xref: /linux/kernel/sched/deadline.c (revision d9043c79ba68a089f95bb4344ab0232c3585f9f1)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Deadline Scheduling Class (SCHED_DEADLINE)
4  *
5  * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
6  *
7  * Tasks that periodically executes their instances for less than their
8  * runtime won't miss any of their deadlines.
9  * Tasks that are not periodic or sporadic or that tries to execute more
10  * than their reserved bandwidth will be slowed down (and may potentially
11  * miss some of their deadlines), and won't affect any other task.
12  *
13  * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>,
14  *                    Juri Lelli <juri.lelli@gmail.com>,
15  *                    Michael Trimarchi <michael@amarulasolutions.com>,
16  *                    Fabio Checconi <fchecconi@gmail.com>
17  */
18 
19 #include <linux/cpuset.h>
20 #include <linux/sched/clock.h>
21 #include <uapi/linux/sched/types.h>
22 #include "sched.h"
23 #include "pelt.h"
24 
25 /*
26  * Default limits for DL period; on the top end we guard against small util
27  * tasks still getting ridiculously long effective runtimes, on the bottom end we
28  * guard against timer DoS.
29  */
30 static unsigned int sysctl_sched_dl_period_max = 1 << 22; /* ~4 seconds */
31 static unsigned int sysctl_sched_dl_period_min = 100;     /* 100 us */
32 #ifdef CONFIG_SYSCTL
33 static const struct ctl_table sched_dl_sysctls[] = {
34 	{
35 		.procname       = "sched_deadline_period_max_us",
36 		.data           = &sysctl_sched_dl_period_max,
37 		.maxlen         = sizeof(unsigned int),
38 		.mode           = 0644,
39 		.proc_handler   = proc_douintvec_minmax,
40 		.extra1         = (void *)&sysctl_sched_dl_period_min,
41 	},
42 	{
43 		.procname       = "sched_deadline_period_min_us",
44 		.data           = &sysctl_sched_dl_period_min,
45 		.maxlen         = sizeof(unsigned int),
46 		.mode           = 0644,
47 		.proc_handler   = proc_douintvec_minmax,
48 		.extra2         = (void *)&sysctl_sched_dl_period_max,
49 	},
50 };
51 
sched_dl_sysctl_init(void)52 static int __init sched_dl_sysctl_init(void)
53 {
54 	register_sysctl_init("kernel", sched_dl_sysctls);
55 	return 0;
56 }
57 late_initcall(sched_dl_sysctl_init);
58 #endif /* CONFIG_SYSCTL */
59 
dl_server(struct sched_dl_entity * dl_se)60 static bool dl_server(struct sched_dl_entity *dl_se)
61 {
62 	return dl_se->dl_server;
63 }
64 
dl_task_of(struct sched_dl_entity * dl_se)65 static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
66 {
67 	BUG_ON(dl_server(dl_se));
68 	return container_of(dl_se, struct task_struct, dl);
69 }
70 
rq_of_dl_rq(struct dl_rq * dl_rq)71 static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
72 {
73 	return container_of(dl_rq, struct rq, dl);
74 }
75 
rq_of_dl_se(struct sched_dl_entity * dl_se)76 static inline struct rq *rq_of_dl_se(struct sched_dl_entity *dl_se)
77 {
78 	struct rq *rq = dl_se->rq;
79 
80 	if (!dl_server(dl_se))
81 		rq = task_rq(dl_task_of(dl_se));
82 
83 	return rq;
84 }
85 
dl_rq_of_se(struct sched_dl_entity * dl_se)86 static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
87 {
88 	return &rq_of_dl_se(dl_se)->dl;
89 }
90 
on_dl_rq(struct sched_dl_entity * dl_se)91 static inline int on_dl_rq(struct sched_dl_entity *dl_se)
92 {
93 	return !RB_EMPTY_NODE(&dl_se->rb_node);
94 }
95 
96 #ifdef CONFIG_RT_MUTEXES
pi_of(struct sched_dl_entity * dl_se)97 static inline struct sched_dl_entity *pi_of(struct sched_dl_entity *dl_se)
98 {
99 	return dl_se->pi_se;
100 }
101 
is_dl_boosted(struct sched_dl_entity * dl_se)102 static inline bool is_dl_boosted(struct sched_dl_entity *dl_se)
103 {
104 	return pi_of(dl_se) != dl_se;
105 }
106 #else /* !CONFIG_RT_MUTEXES: */
pi_of(struct sched_dl_entity * dl_se)107 static inline struct sched_dl_entity *pi_of(struct sched_dl_entity *dl_se)
108 {
109 	return dl_se;
110 }
111 
is_dl_boosted(struct sched_dl_entity * dl_se)112 static inline bool is_dl_boosted(struct sched_dl_entity *dl_se)
113 {
114 	return false;
115 }
116 #endif /* !CONFIG_RT_MUTEXES */
117 
dl_bw_of(int i)118 static inline struct dl_bw *dl_bw_of(int i)
119 {
120 	RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
121 			 "sched RCU must be held");
122 	return &cpu_rq(i)->rd->dl_bw;
123 }
124 
dl_bw_cpus(int i)125 static inline int dl_bw_cpus(int i)
126 {
127 	struct root_domain *rd = cpu_rq(i)->rd;
128 	int cpus;
129 
130 	RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
131 			 "sched RCU must be held");
132 
133 	if (cpumask_subset(rd->span, cpu_active_mask))
134 		return cpumask_weight(rd->span);
135 
136 	cpus = 0;
137 
138 	for_each_cpu_and(i, rd->span, cpu_active_mask)
139 		cpus++;
140 
141 	return cpus;
142 }
143 
__dl_bw_capacity(const struct cpumask * mask)144 static inline unsigned long __dl_bw_capacity(const struct cpumask *mask)
145 {
146 	unsigned long cap = 0;
147 	int i;
148 
149 	for_each_cpu_and(i, mask, cpu_active_mask)
150 		cap += arch_scale_cpu_capacity(i);
151 
152 	return cap;
153 }
154 
155 /*
156  * XXX Fix: If 'rq->rd == def_root_domain' perform AC against capacity
157  * of the CPU the task is running on rather rd's \Sum CPU capacity.
158  */
dl_bw_capacity(int i)159 static inline unsigned long dl_bw_capacity(int i)
160 {
161 	if (!sched_asym_cpucap_active() &&
162 	    arch_scale_cpu_capacity(i) == SCHED_CAPACITY_SCALE) {
163 		return dl_bw_cpus(i) << SCHED_CAPACITY_SHIFT;
164 	} else {
165 		RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
166 				 "sched RCU must be held");
167 
168 		return __dl_bw_capacity(cpu_rq(i)->rd->span);
169 	}
170 }
171 
dl_bw_visited(int cpu,u64 cookie)172 bool dl_bw_visited(int cpu, u64 cookie)
173 {
174 	struct root_domain *rd = cpu_rq(cpu)->rd;
175 
176 	if (rd->visit_cookie == cookie)
177 		return true;
178 
179 	rd->visit_cookie = cookie;
180 	return false;
181 }
182 
183 static inline
__dl_update(struct dl_bw * dl_b,s64 bw)184 void __dl_update(struct dl_bw *dl_b, s64 bw)
185 {
186 	struct root_domain *rd = container_of(dl_b, struct root_domain, dl_bw);
187 	int i;
188 
189 	RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
190 			 "sched RCU must be held");
191 	for_each_cpu_and(i, rd->span, cpu_active_mask) {
192 		struct rq *rq = cpu_rq(i);
193 
194 		rq->dl.extra_bw += bw;
195 	}
196 }
197 
198 static inline
__dl_sub(struct dl_bw * dl_b,u64 tsk_bw,int cpus)199 void __dl_sub(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
200 {
201 	dl_b->total_bw -= tsk_bw;
202 	__dl_update(dl_b, (s32)tsk_bw / cpus);
203 }
204 
205 static inline
__dl_add(struct dl_bw * dl_b,u64 tsk_bw,int cpus)206 void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
207 {
208 	dl_b->total_bw += tsk_bw;
209 	__dl_update(dl_b, -((s32)tsk_bw / cpus));
210 }
211 
212 static inline bool
__dl_overflow(struct dl_bw * dl_b,unsigned long cap,u64 old_bw,u64 new_bw)213 __dl_overflow(struct dl_bw *dl_b, unsigned long cap, u64 old_bw, u64 new_bw)
214 {
215 	return dl_b->bw != -1 &&
216 	       cap_scale(dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw;
217 }
218 
219 static inline
__add_running_bw(u64 dl_bw,struct dl_rq * dl_rq)220 void __add_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
221 {
222 	u64 old = dl_rq->running_bw;
223 
224 	lockdep_assert_rq_held(rq_of_dl_rq(dl_rq));
225 	dl_rq->running_bw += dl_bw;
226 	WARN_ON_ONCE(dl_rq->running_bw < old); /* overflow */
227 	WARN_ON_ONCE(dl_rq->running_bw > dl_rq->this_bw);
228 	/* kick cpufreq (see the comment in kernel/sched/sched.h). */
229 	cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
230 }
231 
232 static inline
__sub_running_bw(u64 dl_bw,struct dl_rq * dl_rq)233 void __sub_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
234 {
235 	u64 old = dl_rq->running_bw;
236 
237 	lockdep_assert_rq_held(rq_of_dl_rq(dl_rq));
238 	dl_rq->running_bw -= dl_bw;
239 	WARN_ON_ONCE(dl_rq->running_bw > old); /* underflow */
240 	if (dl_rq->running_bw > old)
241 		dl_rq->running_bw = 0;
242 	/* kick cpufreq (see the comment in kernel/sched/sched.h). */
243 	cpufreq_update_util(rq_of_dl_rq(dl_rq), 0);
244 }
245 
246 static inline
__add_rq_bw(u64 dl_bw,struct dl_rq * dl_rq)247 void __add_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
248 {
249 	u64 old = dl_rq->this_bw;
250 
251 	lockdep_assert_rq_held(rq_of_dl_rq(dl_rq));
252 	dl_rq->this_bw += dl_bw;
253 	WARN_ON_ONCE(dl_rq->this_bw < old); /* overflow */
254 }
255 
256 static inline
__sub_rq_bw(u64 dl_bw,struct dl_rq * dl_rq)257 void __sub_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
258 {
259 	u64 old = dl_rq->this_bw;
260 
261 	lockdep_assert_rq_held(rq_of_dl_rq(dl_rq));
262 	dl_rq->this_bw -= dl_bw;
263 	WARN_ON_ONCE(dl_rq->this_bw > old); /* underflow */
264 	if (dl_rq->this_bw > old)
265 		dl_rq->this_bw = 0;
266 	WARN_ON_ONCE(dl_rq->running_bw > dl_rq->this_bw);
267 }
268 
269 static inline
add_rq_bw(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)270 void add_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
271 {
272 	if (!dl_entity_is_special(dl_se))
273 		__add_rq_bw(dl_se->dl_bw, dl_rq);
274 }
275 
276 static inline
sub_rq_bw(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)277 void sub_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
278 {
279 	if (!dl_entity_is_special(dl_se))
280 		__sub_rq_bw(dl_se->dl_bw, dl_rq);
281 }
282 
283 static inline
add_running_bw(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)284 void add_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
285 {
286 	if (!dl_entity_is_special(dl_se))
287 		__add_running_bw(dl_se->dl_bw, dl_rq);
288 }
289 
290 static inline
sub_running_bw(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)291 void sub_running_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
292 {
293 	if (!dl_entity_is_special(dl_se))
294 		__sub_running_bw(dl_se->dl_bw, dl_rq);
295 }
296 
dl_rq_change_utilization(struct rq * rq,struct sched_dl_entity * dl_se,u64 new_bw)297 static void dl_rq_change_utilization(struct rq *rq, struct sched_dl_entity *dl_se, u64 new_bw)
298 {
299 	if (dl_se->dl_non_contending) {
300 		sub_running_bw(dl_se, &rq->dl);
301 		dl_se->dl_non_contending = 0;
302 
303 		/*
304 		 * If the timer handler is currently running and the
305 		 * timer cannot be canceled, inactive_task_timer()
306 		 * will see that dl_not_contending is not set, and
307 		 * will not touch the rq's active utilization,
308 		 * so we are still safe.
309 		 */
310 		if (hrtimer_try_to_cancel(&dl_se->inactive_timer) == 1) {
311 			if (!dl_server(dl_se))
312 				put_task_struct(dl_task_of(dl_se));
313 		}
314 	}
315 	__sub_rq_bw(dl_se->dl_bw, &rq->dl);
316 	__add_rq_bw(new_bw, &rq->dl);
317 }
318 
319 static __always_inline
cancel_dl_timer(struct sched_dl_entity * dl_se,struct hrtimer * timer)320 void cancel_dl_timer(struct sched_dl_entity *dl_se, struct hrtimer *timer)
321 {
322 	/*
323 	 * If the timer callback was running (hrtimer_try_to_cancel == -1),
324 	 * it will eventually call put_task_struct().
325 	 */
326 	if (hrtimer_try_to_cancel(timer) == 1 && !dl_server(dl_se))
327 		put_task_struct(dl_task_of(dl_se));
328 }
329 
330 static __always_inline
cancel_replenish_timer(struct sched_dl_entity * dl_se)331 void cancel_replenish_timer(struct sched_dl_entity *dl_se)
332 {
333 	cancel_dl_timer(dl_se, &dl_se->dl_timer);
334 }
335 
336 static __always_inline
cancel_inactive_timer(struct sched_dl_entity * dl_se)337 void cancel_inactive_timer(struct sched_dl_entity *dl_se)
338 {
339 	cancel_dl_timer(dl_se, &dl_se->inactive_timer);
340 }
341 
dl_change_utilization(struct task_struct * p,u64 new_bw)342 static void dl_change_utilization(struct task_struct *p, u64 new_bw)
343 {
344 	WARN_ON_ONCE(p->dl.flags & SCHED_FLAG_SUGOV);
345 
346 	if (task_on_rq_queued(p))
347 		return;
348 
349 	dl_rq_change_utilization(task_rq(p), &p->dl, new_bw);
350 }
351 
352 static void __dl_clear_params(struct sched_dl_entity *dl_se);
353 
354 /*
355  * The utilization of a task cannot be immediately removed from
356  * the rq active utilization (running_bw) when the task blocks.
357  * Instead, we have to wait for the so called "0-lag time".
358  *
359  * If a task blocks before the "0-lag time", a timer (the inactive
360  * timer) is armed, and running_bw is decreased when the timer
361  * fires.
362  *
363  * If the task wakes up again before the inactive timer fires,
364  * the timer is canceled, whereas if the task wakes up after the
365  * inactive timer fired (and running_bw has been decreased) the
366  * task's utilization has to be added to running_bw again.
367  * A flag in the deadline scheduling entity (dl_non_contending)
368  * is used to avoid race conditions between the inactive timer handler
369  * and task wakeups.
370  *
371  * The following diagram shows how running_bw is updated. A task is
372  * "ACTIVE" when its utilization contributes to running_bw; an
373  * "ACTIVE contending" task is in the TASK_RUNNING state, while an
374  * "ACTIVE non contending" task is a blocked task for which the "0-lag time"
375  * has not passed yet. An "INACTIVE" task is a task for which the "0-lag"
376  * time already passed, which does not contribute to running_bw anymore.
377  *                              +------------------+
378  *             wakeup           |    ACTIVE        |
379  *          +------------------>+   contending     |
380  *          | add_running_bw    |                  |
381  *          |                   +----+------+------+
382  *          |                        |      ^
383  *          |                dequeue |      |
384  * +--------+-------+                |      |
385  * |                |   t >= 0-lag   |      | wakeup
386  * |    INACTIVE    |<---------------+      |
387  * |                | sub_running_bw |      |
388  * +--------+-------+                |      |
389  *          ^                        |      |
390  *          |              t < 0-lag |      |
391  *          |                        |      |
392  *          |                        V      |
393  *          |                   +----+------+------+
394  *          | sub_running_bw    |    ACTIVE        |
395  *          +-------------------+                  |
396  *            inactive timer    |  non contending  |
397  *            fired             +------------------+
398  *
399  * The task_non_contending() function is invoked when a task
400  * blocks, and checks if the 0-lag time already passed or
401  * not (in the first case, it directly updates running_bw;
402  * in the second case, it arms the inactive timer).
403  *
404  * The task_contending() function is invoked when a task wakes
405  * up, and checks if the task is still in the "ACTIVE non contending"
406  * state or not (in the second case, it updates running_bw).
407  */
task_non_contending(struct sched_dl_entity * dl_se)408 static void task_non_contending(struct sched_dl_entity *dl_se)
409 {
410 	struct hrtimer *timer = &dl_se->inactive_timer;
411 	struct rq *rq = rq_of_dl_se(dl_se);
412 	struct dl_rq *dl_rq = &rq->dl;
413 	s64 zerolag_time;
414 
415 	/*
416 	 * If this is a non-deadline task that has been boosted,
417 	 * do nothing
418 	 */
419 	if (dl_se->dl_runtime == 0)
420 		return;
421 
422 	if (dl_entity_is_special(dl_se))
423 		return;
424 
425 	WARN_ON(dl_se->dl_non_contending);
426 
427 	zerolag_time = dl_se->deadline -
428 		 div64_long((dl_se->runtime * dl_se->dl_period),
429 			dl_se->dl_runtime);
430 
431 	/*
432 	 * Using relative times instead of the absolute "0-lag time"
433 	 * allows to simplify the code
434 	 */
435 	zerolag_time -= rq_clock(rq);
436 
437 	/*
438 	 * If the "0-lag time" already passed, decrease the active
439 	 * utilization now, instead of starting a timer
440 	 */
441 	if ((zerolag_time < 0) || hrtimer_active(&dl_se->inactive_timer)) {
442 		if (dl_server(dl_se)) {
443 			sub_running_bw(dl_se, dl_rq);
444 		} else {
445 			struct task_struct *p = dl_task_of(dl_se);
446 
447 			if (dl_task(p))
448 				sub_running_bw(dl_se, dl_rq);
449 
450 			if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) {
451 				struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
452 
453 				if (READ_ONCE(p->__state) == TASK_DEAD)
454 					sub_rq_bw(dl_se, &rq->dl);
455 				raw_spin_lock(&dl_b->lock);
456 				__dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(task_cpu(p)));
457 				raw_spin_unlock(&dl_b->lock);
458 				__dl_clear_params(dl_se);
459 			}
460 		}
461 
462 		return;
463 	}
464 
465 	dl_se->dl_non_contending = 1;
466 	if (!dl_server(dl_se))
467 		get_task_struct(dl_task_of(dl_se));
468 
469 	hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL_HARD);
470 }
471 
task_contending(struct sched_dl_entity * dl_se,int flags)472 static void task_contending(struct sched_dl_entity *dl_se, int flags)
473 {
474 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
475 
476 	/*
477 	 * If this is a non-deadline task that has been boosted,
478 	 * do nothing
479 	 */
480 	if (dl_se->dl_runtime == 0)
481 		return;
482 
483 	if (flags & ENQUEUE_MIGRATED)
484 		add_rq_bw(dl_se, dl_rq);
485 
486 	if (dl_se->dl_non_contending) {
487 		dl_se->dl_non_contending = 0;
488 		/*
489 		 * If the timer handler is currently running and the
490 		 * timer cannot be canceled, inactive_task_timer()
491 		 * will see that dl_not_contending is not set, and
492 		 * will not touch the rq's active utilization,
493 		 * so we are still safe.
494 		 */
495 		cancel_inactive_timer(dl_se);
496 	} else {
497 		/*
498 		 * Since "dl_non_contending" is not set, the
499 		 * task's utilization has already been removed from
500 		 * active utilization (either when the task blocked,
501 		 * when the "inactive timer" fired).
502 		 * So, add it back.
503 		 */
504 		add_running_bw(dl_se, dl_rq);
505 	}
506 }
507 
is_leftmost(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)508 static inline int is_leftmost(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
509 {
510 	return rb_first_cached(&dl_rq->root) == &dl_se->rb_node;
511 }
512 
513 static void init_dl_rq_bw_ratio(struct dl_rq *dl_rq);
514 
init_dl_bw(struct dl_bw * dl_b)515 void init_dl_bw(struct dl_bw *dl_b)
516 {
517 	raw_spin_lock_init(&dl_b->lock);
518 	if (global_rt_runtime() == RUNTIME_INF)
519 		dl_b->bw = -1;
520 	else
521 		dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
522 	dl_b->total_bw = 0;
523 }
524 
init_dl_rq(struct dl_rq * dl_rq)525 void init_dl_rq(struct dl_rq *dl_rq)
526 {
527 	dl_rq->root = RB_ROOT_CACHED;
528 
529 	/* zero means no -deadline tasks */
530 	dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;
531 
532 	dl_rq->overloaded = 0;
533 	dl_rq->pushable_dl_tasks_root = RB_ROOT_CACHED;
534 
535 	dl_rq->running_bw = 0;
536 	dl_rq->this_bw = 0;
537 	init_dl_rq_bw_ratio(dl_rq);
538 }
539 
dl_overloaded(struct rq * rq)540 static inline int dl_overloaded(struct rq *rq)
541 {
542 	return atomic_read(&rq->rd->dlo_count);
543 }
544 
dl_set_overload(struct rq * rq)545 static inline void dl_set_overload(struct rq *rq)
546 {
547 	if (!rq->online)
548 		return;
549 
550 	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
551 	/*
552 	 * Must be visible before the overload count is
553 	 * set (as in sched_rt.c).
554 	 *
555 	 * Matched by the barrier in pull_dl_task().
556 	 */
557 	smp_wmb();
558 	atomic_inc(&rq->rd->dlo_count);
559 }
560 
dl_clear_overload(struct rq * rq)561 static inline void dl_clear_overload(struct rq *rq)
562 {
563 	if (!rq->online)
564 		return;
565 
566 	atomic_dec(&rq->rd->dlo_count);
567 	cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
568 }
569 
570 #define __node_2_pdl(node) \
571 	rb_entry((node), struct task_struct, pushable_dl_tasks)
572 
__pushable_less(struct rb_node * a,const struct rb_node * b)573 static inline bool __pushable_less(struct rb_node *a, const struct rb_node *b)
574 {
575 	return dl_entity_preempt(&__node_2_pdl(a)->dl, &__node_2_pdl(b)->dl);
576 }
577 
has_pushable_dl_tasks(struct rq * rq)578 static inline int has_pushable_dl_tasks(struct rq *rq)
579 {
580 	return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root.rb_root);
581 }
582 
583 /*
584  * The list of pushable -deadline task is not a plist, like in
585  * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
586  */
enqueue_pushable_dl_task(struct rq * rq,struct task_struct * p)587 static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
588 {
589 	struct rb_node *leftmost;
590 
591 	WARN_ON_ONCE(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
592 
593 	leftmost = rb_add_cached(&p->pushable_dl_tasks,
594 				 &rq->dl.pushable_dl_tasks_root,
595 				 __pushable_less);
596 	if (leftmost)
597 		rq->dl.earliest_dl.next = p->dl.deadline;
598 
599 	if (!rq->dl.overloaded) {
600 		dl_set_overload(rq);
601 		rq->dl.overloaded = 1;
602 	}
603 }
604 
dequeue_pushable_dl_task(struct rq * rq,struct task_struct * p)605 static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
606 {
607 	struct dl_rq *dl_rq = &rq->dl;
608 	struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root;
609 	struct rb_node *leftmost;
610 
611 	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
612 		return;
613 
614 	leftmost = rb_erase_cached(&p->pushable_dl_tasks, root);
615 	if (leftmost)
616 		dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline;
617 
618 	RB_CLEAR_NODE(&p->pushable_dl_tasks);
619 
620 	if (!has_pushable_dl_tasks(rq) && rq->dl.overloaded) {
621 		dl_clear_overload(rq);
622 		rq->dl.overloaded = 0;
623 	}
624 }
625 
626 static int push_dl_task(struct rq *rq);
627 
need_pull_dl_task(struct rq * rq,struct task_struct * prev)628 static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
629 {
630 	return rq->online && dl_task(prev);
631 }
632 
633 static DEFINE_PER_CPU(struct balance_callback, dl_push_head);
634 static DEFINE_PER_CPU(struct balance_callback, dl_pull_head);
635 
636 static void push_dl_tasks(struct rq *);
637 static void pull_dl_task(struct rq *);
638 
deadline_queue_push_tasks(struct rq * rq)639 static inline void deadline_queue_push_tasks(struct rq *rq)
640 {
641 	if (!has_pushable_dl_tasks(rq))
642 		return;
643 
644 	queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
645 }
646 
deadline_queue_pull_task(struct rq * rq)647 static inline void deadline_queue_pull_task(struct rq *rq)
648 {
649 	queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task);
650 }
651 
652 static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);
653 
dl_task_offline_migration(struct rq * rq,struct task_struct * p)654 static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p)
655 {
656 	struct rq *later_rq = NULL;
657 	struct dl_bw *dl_b;
658 
659 	later_rq = find_lock_later_rq(p, rq);
660 	if (!later_rq) {
661 		int cpu;
662 
663 		/*
664 		 * If we cannot preempt any rq, fall back to pick any
665 		 * online CPU:
666 		 */
667 		cpu = cpumask_any_and(cpu_active_mask, p->cpus_ptr);
668 		if (cpu >= nr_cpu_ids) {
669 			/*
670 			 * Failed to find any suitable CPU.
671 			 * The task will never come back!
672 			 */
673 			WARN_ON_ONCE(dl_bandwidth_enabled());
674 
675 			/*
676 			 * If admission control is disabled we
677 			 * try a little harder to let the task
678 			 * run.
679 			 */
680 			cpu = cpumask_any(cpu_active_mask);
681 		}
682 		later_rq = cpu_rq(cpu);
683 		double_lock_balance(rq, later_rq);
684 	}
685 
686 	if (p->dl.dl_non_contending || p->dl.dl_throttled) {
687 		/*
688 		 * Inactive timer is armed (or callback is running, but
689 		 * waiting for us to release rq locks). In any case, when it
690 		 * will fire (or continue), it will see running_bw of this
691 		 * task migrated to later_rq (and correctly handle it).
692 		 */
693 		sub_running_bw(&p->dl, &rq->dl);
694 		sub_rq_bw(&p->dl, &rq->dl);
695 
696 		add_rq_bw(&p->dl, &later_rq->dl);
697 		add_running_bw(&p->dl, &later_rq->dl);
698 	} else {
699 		sub_rq_bw(&p->dl, &rq->dl);
700 		add_rq_bw(&p->dl, &later_rq->dl);
701 	}
702 
703 	/*
704 	 * And we finally need to fix up root_domain(s) bandwidth accounting,
705 	 * since p is still hanging out in the old (now moved to default) root
706 	 * domain.
707 	 */
708 	dl_b = &rq->rd->dl_bw;
709 	raw_spin_lock(&dl_b->lock);
710 	__dl_sub(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span));
711 	raw_spin_unlock(&dl_b->lock);
712 
713 	dl_b = &later_rq->rd->dl_bw;
714 	raw_spin_lock(&dl_b->lock);
715 	__dl_add(dl_b, p->dl.dl_bw, cpumask_weight(later_rq->rd->span));
716 	raw_spin_unlock(&dl_b->lock);
717 
718 	set_task_cpu(p, later_rq->cpu);
719 	double_unlock_balance(later_rq, rq);
720 
721 	return later_rq;
722 }
723 
724 static void
725 enqueue_dl_entity(struct sched_dl_entity *dl_se, int flags);
726 static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
727 static void dequeue_dl_entity(struct sched_dl_entity *dl_se, int flags);
728 static void wakeup_preempt_dl(struct rq *rq, struct task_struct *p, int flags);
729 
replenish_dl_new_period(struct sched_dl_entity * dl_se,struct rq * rq)730 static inline void replenish_dl_new_period(struct sched_dl_entity *dl_se,
731 					    struct rq *rq)
732 {
733 	/* for non-boosted task, pi_of(dl_se) == dl_se */
734 	dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
735 	dl_se->runtime = pi_of(dl_se)->dl_runtime;
736 
737 	/*
738 	 * If it is a deferred reservation, and the server
739 	 * is not handling an starvation case, defer it.
740 	 */
741 	if (dl_se->dl_defer && !dl_se->dl_defer_running) {
742 		dl_se->dl_throttled = 1;
743 		dl_se->dl_defer_armed = 1;
744 	}
745 }
746 
747 /*
748  * We are being explicitly informed that a new instance is starting,
749  * and this means that:
750  *  - the absolute deadline of the entity has to be placed at
751  *    current time + relative deadline;
752  *  - the runtime of the entity has to be set to the maximum value.
753  *
754  * The capability of specifying such event is useful whenever a -deadline
755  * entity wants to (try to!) synchronize its behaviour with the scheduler's
756  * one, and to (try to!) reconcile itself with its own scheduling
757  * parameters.
758  */
setup_new_dl_entity(struct sched_dl_entity * dl_se)759 static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
760 {
761 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
762 	struct rq *rq = rq_of_dl_rq(dl_rq);
763 
764 	update_rq_clock(rq);
765 
766 	WARN_ON(is_dl_boosted(dl_se));
767 	WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline));
768 
769 	/*
770 	 * We are racing with the deadline timer. So, do nothing because
771 	 * the deadline timer handler will take care of properly recharging
772 	 * the runtime and postponing the deadline
773 	 */
774 	if (dl_se->dl_throttled)
775 		return;
776 
777 	/*
778 	 * We use the regular wall clock time to set deadlines in the
779 	 * future; in fact, we must consider execution overheads (time
780 	 * spent on hardirq context, etc.).
781 	 */
782 	replenish_dl_new_period(dl_se, rq);
783 }
784 
785 static int start_dl_timer(struct sched_dl_entity *dl_se);
786 static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t);
787 
788 /*
789  * Pure Earliest Deadline First (EDF) scheduling does not deal with the
790  * possibility of a entity lasting more than what it declared, and thus
791  * exhausting its runtime.
792  *
793  * Here we are interested in making runtime overrun possible, but we do
794  * not want a entity which is misbehaving to affect the scheduling of all
795  * other entities.
796  * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
797  * is used, in order to confine each entity within its own bandwidth.
798  *
799  * This function deals exactly with that, and ensures that when the runtime
800  * of a entity is replenished, its deadline is also postponed. That ensures
801  * the overrunning entity can't interfere with other entity in the system and
802  * can't make them miss their deadlines. Reasons why this kind of overruns
803  * could happen are, typically, a entity voluntarily trying to overcome its
804  * runtime, or it just underestimated it during sched_setattr().
805  */
replenish_dl_entity(struct sched_dl_entity * dl_se)806 static void replenish_dl_entity(struct sched_dl_entity *dl_se)
807 {
808 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
809 	struct rq *rq = rq_of_dl_rq(dl_rq);
810 
811 	WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0);
812 
813 	/*
814 	 * This could be the case for a !-dl task that is boosted.
815 	 * Just go with full inherited parameters.
816 	 *
817 	 * Or, it could be the case of a deferred reservation that
818 	 * was not able to consume its runtime in background and
819 	 * reached this point with current u > U.
820 	 *
821 	 * In both cases, set a new period.
822 	 */
823 	if (dl_se->dl_deadline == 0 ||
824 	    (dl_se->dl_defer_armed && dl_entity_overflow(dl_se, rq_clock(rq)))) {
825 		dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
826 		dl_se->runtime = pi_of(dl_se)->dl_runtime;
827 	}
828 
829 	if (dl_se->dl_yielded && dl_se->runtime > 0)
830 		dl_se->runtime = 0;
831 
832 	/*
833 	 * We keep moving the deadline away until we get some
834 	 * available runtime for the entity. This ensures correct
835 	 * handling of situations where the runtime overrun is
836 	 * arbitrary large.
837 	 */
838 	while (dl_se->runtime <= 0) {
839 		dl_se->deadline += pi_of(dl_se)->dl_period;
840 		dl_se->runtime += pi_of(dl_se)->dl_runtime;
841 	}
842 
843 	/*
844 	 * At this point, the deadline really should be "in
845 	 * the future" with respect to rq->clock. If it's
846 	 * not, we are, for some reason, lagging too much!
847 	 * Anyway, after having warn userspace abut that,
848 	 * we still try to keep the things running by
849 	 * resetting the deadline and the budget of the
850 	 * entity.
851 	 */
852 	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
853 		printk_deferred_once("sched: DL replenish lagged too much\n");
854 		replenish_dl_new_period(dl_se, rq);
855 	}
856 
857 	if (dl_se->dl_yielded)
858 		dl_se->dl_yielded = 0;
859 	if (dl_se->dl_throttled)
860 		dl_se->dl_throttled = 0;
861 
862 	/*
863 	 * If this is the replenishment of a deferred reservation,
864 	 * clear the flag and return.
865 	 */
866 	if (dl_se->dl_defer_armed) {
867 		dl_se->dl_defer_armed = 0;
868 		return;
869 	}
870 
871 	/*
872 	 * A this point, if the deferred server is not armed, and the deadline
873 	 * is in the future, if it is not running already, throttle the server
874 	 * and arm the defer timer.
875 	 */
876 	if (dl_se->dl_defer && !dl_se->dl_defer_running &&
877 	    dl_time_before(rq_clock(dl_se->rq), dl_se->deadline - dl_se->runtime)) {
878 		if (!is_dl_boosted(dl_se)) {
879 
880 			/*
881 			 * Set dl_se->dl_defer_armed and dl_throttled variables to
882 			 * inform the start_dl_timer() that this is a deferred
883 			 * activation.
884 			 */
885 			dl_se->dl_defer_armed = 1;
886 			dl_se->dl_throttled = 1;
887 			if (!start_dl_timer(dl_se)) {
888 				/*
889 				 * If for whatever reason (delays), a previous timer was
890 				 * queued but not serviced, cancel it and clean the
891 				 * deferrable server variables intended for start_dl_timer().
892 				 */
893 				hrtimer_try_to_cancel(&dl_se->dl_timer);
894 				dl_se->dl_defer_armed = 0;
895 				dl_se->dl_throttled = 0;
896 			}
897 		}
898 	}
899 }
900 
901 /*
902  * Here we check if --at time t-- an entity (which is probably being
903  * [re]activated or, in general, enqueued) can use its remaining runtime
904  * and its current deadline _without_ exceeding the bandwidth it is
905  * assigned (function returns true if it can't). We are in fact applying
906  * one of the CBS rules: when a task wakes up, if the residual runtime
907  * over residual deadline fits within the allocated bandwidth, then we
908  * can keep the current (absolute) deadline and residual budget without
909  * disrupting the schedulability of the system. Otherwise, we should
910  * refill the runtime and set the deadline a period in the future,
911  * because keeping the current (absolute) deadline of the task would
912  * result in breaking guarantees promised to other tasks (refer to
913  * Documentation/scheduler/sched-deadline.rst for more information).
914  *
915  * This function returns true if:
916  *
917  *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
918  *
919  * IOW we can't recycle current parameters.
920  *
921  * Notice that the bandwidth check is done against the deadline. For
922  * task with deadline equal to period this is the same of using
923  * dl_period instead of dl_deadline in the equation above.
924  */
dl_entity_overflow(struct sched_dl_entity * dl_se,u64 t)925 static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
926 {
927 	u64 left, right;
928 
929 	/*
930 	 * left and right are the two sides of the equation above,
931 	 * after a bit of shuffling to use multiplications instead
932 	 * of divisions.
933 	 *
934 	 * Note that none of the time values involved in the two
935 	 * multiplications are absolute: dl_deadline and dl_runtime
936 	 * are the relative deadline and the maximum runtime of each
937 	 * instance, runtime is the runtime left for the last instance
938 	 * and (deadline - t), since t is rq->clock, is the time left
939 	 * to the (absolute) deadline. Even if overflowing the u64 type
940 	 * is very unlikely to occur in both cases, here we scale down
941 	 * as we want to avoid that risk at all. Scaling down by 10
942 	 * means that we reduce granularity to 1us. We are fine with it,
943 	 * since this is only a true/false check and, anyway, thinking
944 	 * of anything below microseconds resolution is actually fiction
945 	 * (but still we want to give the user that illusion >;).
946 	 */
947 	left = (pi_of(dl_se)->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
948 	right = ((dl_se->deadline - t) >> DL_SCALE) *
949 		(pi_of(dl_se)->dl_runtime >> DL_SCALE);
950 
951 	return dl_time_before(right, left);
952 }
953 
954 /*
955  * Revised wakeup rule [1]: For self-suspending tasks, rather then
956  * re-initializing task's runtime and deadline, the revised wakeup
957  * rule adjusts the task's runtime to avoid the task to overrun its
958  * density.
959  *
960  * Reasoning: a task may overrun the density if:
961  *    runtime / (deadline - t) > dl_runtime / dl_deadline
962  *
963  * Therefore, runtime can be adjusted to:
964  *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
965  *
966  * In such way that runtime will be equal to the maximum density
967  * the task can use without breaking any rule.
968  *
969  * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
970  * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
971  */
972 static void
update_dl_revised_wakeup(struct sched_dl_entity * dl_se,struct rq * rq)973 update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
974 {
975 	u64 laxity = dl_se->deadline - rq_clock(rq);
976 
977 	/*
978 	 * If the task has deadline < period, and the deadline is in the past,
979 	 * it should already be throttled before this check.
980 	 *
981 	 * See update_dl_entity() comments for further details.
982 	 */
983 	WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));
984 
985 	dl_se->runtime = (dl_se->dl_density * laxity) >> BW_SHIFT;
986 }
987 
988 /*
989  * Regarding the deadline, a task with implicit deadline has a relative
990  * deadline == relative period. A task with constrained deadline has a
991  * relative deadline <= relative period.
992  *
993  * We support constrained deadline tasks. However, there are some restrictions
994  * applied only for tasks which do not have an implicit deadline. See
995  * update_dl_entity() to know more about such restrictions.
996  *
997  * The dl_is_implicit() returns true if the task has an implicit deadline.
998  */
dl_is_implicit(struct sched_dl_entity * dl_se)999 static inline bool dl_is_implicit(struct sched_dl_entity *dl_se)
1000 {
1001 	return dl_se->dl_deadline == dl_se->dl_period;
1002 }
1003 
1004 /*
1005  * When a deadline entity is placed in the runqueue, its runtime and deadline
1006  * might need to be updated. This is done by a CBS wake up rule. There are two
1007  * different rules: 1) the original CBS; and 2) the Revisited CBS.
1008  *
1009  * When the task is starting a new period, the Original CBS is used. In this
1010  * case, the runtime is replenished and a new absolute deadline is set.
1011  *
1012  * When a task is queued before the begin of the next period, using the
1013  * remaining runtime and deadline could make the entity to overflow, see
1014  * dl_entity_overflow() to find more about runtime overflow. When such case
1015  * is detected, the runtime and deadline need to be updated.
1016  *
1017  * If the task has an implicit deadline, i.e., deadline == period, the Original
1018  * CBS is applied. The runtime is replenished and a new absolute deadline is
1019  * set, as in the previous cases.
1020  *
1021  * However, the Original CBS does not work properly for tasks with
1022  * deadline < period, which are said to have a constrained deadline. By
1023  * applying the Original CBS, a constrained deadline task would be able to run
1024  * runtime/deadline in a period. With deadline < period, the task would
1025  * overrun the runtime/period allowed bandwidth, breaking the admission test.
1026  *
1027  * In order to prevent this misbehave, the Revisited CBS is used for
1028  * constrained deadline tasks when a runtime overflow is detected. In the
1029  * Revisited CBS, rather than replenishing & setting a new absolute deadline,
1030  * the remaining runtime of the task is reduced to avoid runtime overflow.
1031  * Please refer to the comments update_dl_revised_wakeup() function to find
1032  * more about the Revised CBS rule.
1033  */
update_dl_entity(struct sched_dl_entity * dl_se)1034 static void update_dl_entity(struct sched_dl_entity *dl_se)
1035 {
1036 	struct rq *rq = rq_of_dl_se(dl_se);
1037 
1038 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
1039 	    dl_entity_overflow(dl_se, rq_clock(rq))) {
1040 
1041 		if (unlikely(!dl_is_implicit(dl_se) &&
1042 			     !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
1043 			     !is_dl_boosted(dl_se))) {
1044 			update_dl_revised_wakeup(dl_se, rq);
1045 			return;
1046 		}
1047 
1048 		replenish_dl_new_period(dl_se, rq);
1049 	} else if (dl_server(dl_se) && dl_se->dl_defer) {
1050 		/*
1051 		 * The server can still use its previous deadline, so check if
1052 		 * it left the dl_defer_running state.
1053 		 */
1054 		if (!dl_se->dl_defer_running) {
1055 			dl_se->dl_defer_armed = 1;
1056 			dl_se->dl_throttled = 1;
1057 		}
1058 	}
1059 }
1060 
dl_next_period(struct sched_dl_entity * dl_se)1061 static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
1062 {
1063 	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
1064 }
1065 
1066 /*
1067  * If the entity depleted all its runtime, and if we want it to sleep
1068  * while waiting for some new execution time to become available, we
1069  * set the bandwidth replenishment timer to the replenishment instant
1070  * and try to activate it.
1071  *
1072  * Notice that it is important for the caller to know if the timer
1073  * actually started or not (i.e., the replenishment instant is in
1074  * the future or in the past).
1075  */
start_dl_timer(struct sched_dl_entity * dl_se)1076 static int start_dl_timer(struct sched_dl_entity *dl_se)
1077 {
1078 	struct hrtimer *timer = &dl_se->dl_timer;
1079 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1080 	struct rq *rq = rq_of_dl_rq(dl_rq);
1081 	ktime_t now, act;
1082 	s64 delta;
1083 
1084 	lockdep_assert_rq_held(rq);
1085 
1086 	/*
1087 	 * We want the timer to fire at the deadline, but considering
1088 	 * that it is actually coming from rq->clock and not from
1089 	 * hrtimer's time base reading.
1090 	 *
1091 	 * The deferred reservation will have its timer set to
1092 	 * (deadline - runtime). At that point, the CBS rule will decide
1093 	 * if the current deadline can be used, or if a replenishment is
1094 	 * required to avoid add too much pressure on the system
1095 	 * (current u > U).
1096 	 */
1097 	if (dl_se->dl_defer_armed) {
1098 		WARN_ON_ONCE(!dl_se->dl_throttled);
1099 		act = ns_to_ktime(dl_se->deadline - dl_se->runtime);
1100 	} else {
1101 		/* act = deadline - rel-deadline + period */
1102 		act = ns_to_ktime(dl_next_period(dl_se));
1103 	}
1104 
1105 	now = hrtimer_cb_get_time(timer);
1106 	delta = ktime_to_ns(now) - rq_clock(rq);
1107 	act = ktime_add_ns(act, delta);
1108 
1109 	/*
1110 	 * If the expiry time already passed, e.g., because the value
1111 	 * chosen as the deadline is too small, don't even try to
1112 	 * start the timer in the past!
1113 	 */
1114 	if (ktime_us_delta(act, now) < 0)
1115 		return 0;
1116 
1117 	/*
1118 	 * !enqueued will guarantee another callback; even if one is already in
1119 	 * progress. This ensures a balanced {get,put}_task_struct().
1120 	 *
1121 	 * The race against __run_timer() clearing the enqueued state is
1122 	 * harmless because we're holding task_rq()->lock, therefore the timer
1123 	 * expiring after we've done the check will wait on its task_rq_lock()
1124 	 * and observe our state.
1125 	 */
1126 	if (!hrtimer_is_queued(timer)) {
1127 		if (!dl_server(dl_se))
1128 			get_task_struct(dl_task_of(dl_se));
1129 		hrtimer_start(timer, act, HRTIMER_MODE_ABS_HARD);
1130 	}
1131 
1132 	return 1;
1133 }
1134 
__push_dl_task(struct rq * rq,struct rq_flags * rf)1135 static void __push_dl_task(struct rq *rq, struct rq_flags *rf)
1136 {
1137 	/*
1138 	 * Queueing this task back might have overloaded rq, check if we need
1139 	 * to kick someone away.
1140 	 */
1141 	if (has_pushable_dl_tasks(rq)) {
1142 		/*
1143 		 * Nothing relies on rq->lock after this, so its safe to drop
1144 		 * rq->lock.
1145 		 */
1146 		rq_unpin_lock(rq, rf);
1147 		push_dl_task(rq);
1148 		rq_repin_lock(rq, rf);
1149 	}
1150 }
1151 
1152 /* a defer timer will not be reset if the runtime consumed was < dl_server_min_res */
1153 static const u64 dl_server_min_res = 1 * NSEC_PER_MSEC;
1154 
dl_server_timer(struct hrtimer * timer,struct sched_dl_entity * dl_se)1155 static enum hrtimer_restart dl_server_timer(struct hrtimer *timer, struct sched_dl_entity *dl_se)
1156 {
1157 	struct rq *rq = rq_of_dl_se(dl_se);
1158 	u64 fw;
1159 
1160 	scoped_guard (rq_lock, rq) {
1161 		struct rq_flags *rf = &scope.rf;
1162 
1163 		if (!dl_se->dl_throttled || !dl_se->dl_runtime)
1164 			return HRTIMER_NORESTART;
1165 
1166 		sched_clock_tick();
1167 		update_rq_clock(rq);
1168 
1169 		if (!dl_se->dl_runtime)
1170 			return HRTIMER_NORESTART;
1171 
1172 		if (dl_se->dl_defer_armed) {
1173 			/*
1174 			 * First check if the server could consume runtime in background.
1175 			 * If so, it is possible to push the defer timer for this amount
1176 			 * of time. The dl_server_min_res serves as a limit to avoid
1177 			 * forwarding the timer for a too small amount of time.
1178 			 */
1179 			if (dl_time_before(rq_clock(dl_se->rq),
1180 					   (dl_se->deadline - dl_se->runtime - dl_server_min_res))) {
1181 
1182 				/* reset the defer timer */
1183 				fw = dl_se->deadline - rq_clock(dl_se->rq) - dl_se->runtime;
1184 
1185 				hrtimer_forward_now(timer, ns_to_ktime(fw));
1186 				return HRTIMER_RESTART;
1187 			}
1188 
1189 			dl_se->dl_defer_running = 1;
1190 		}
1191 
1192 		enqueue_dl_entity(dl_se, ENQUEUE_REPLENISH);
1193 
1194 		if (!dl_task(dl_se->rq->curr) || dl_entity_preempt(dl_se, &dl_se->rq->curr->dl))
1195 			resched_curr(rq);
1196 
1197 		__push_dl_task(rq, rf);
1198 	}
1199 
1200 	return HRTIMER_NORESTART;
1201 }
1202 
1203 /*
1204  * This is the bandwidth enforcement timer callback. If here, we know
1205  * a task is not on its dl_rq, since the fact that the timer was running
1206  * means the task is throttled and needs a runtime replenishment.
1207  *
1208  * However, what we actually do depends on the fact the task is active,
1209  * (it is on its rq) or has been removed from there by a call to
1210  * dequeue_task_dl(). In the former case we must issue the runtime
1211  * replenishment and add the task back to the dl_rq; in the latter, we just
1212  * do nothing but clearing dl_throttled, so that runtime and deadline
1213  * updating (and the queueing back to dl_rq) will be done by the
1214  * next call to enqueue_task_dl().
1215  */
dl_task_timer(struct hrtimer * timer)1216 static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
1217 {
1218 	struct sched_dl_entity *dl_se = container_of(timer,
1219 						     struct sched_dl_entity,
1220 						     dl_timer);
1221 	struct task_struct *p;
1222 	struct rq_flags rf;
1223 	struct rq *rq;
1224 
1225 	if (dl_server(dl_se))
1226 		return dl_server_timer(timer, dl_se);
1227 
1228 	p = dl_task_of(dl_se);
1229 	rq = task_rq_lock(p, &rf);
1230 
1231 	/*
1232 	 * The task might have changed its scheduling policy to something
1233 	 * different than SCHED_DEADLINE (through switched_from_dl()).
1234 	 */
1235 	if (!dl_task(p))
1236 		goto unlock;
1237 
1238 	/*
1239 	 * The task might have been boosted by someone else and might be in the
1240 	 * boosting/deboosting path, its not throttled.
1241 	 */
1242 	if (is_dl_boosted(dl_se))
1243 		goto unlock;
1244 
1245 	/*
1246 	 * Spurious timer due to start_dl_timer() race; or we already received
1247 	 * a replenishment from rt_mutex_setprio().
1248 	 */
1249 	if (!dl_se->dl_throttled)
1250 		goto unlock;
1251 
1252 	sched_clock_tick();
1253 	update_rq_clock(rq);
1254 
1255 	/*
1256 	 * If the throttle happened during sched-out; like:
1257 	 *
1258 	 *   schedule()
1259 	 *     deactivate_task()
1260 	 *       dequeue_task_dl()
1261 	 *         update_curr_dl()
1262 	 *           start_dl_timer()
1263 	 *         __dequeue_task_dl()
1264 	 *     prev->on_rq = 0;
1265 	 *
1266 	 * We can be both throttled and !queued. Replenish the counter
1267 	 * but do not enqueue -- wait for our wakeup to do that.
1268 	 */
1269 	if (!task_on_rq_queued(p)) {
1270 		replenish_dl_entity(dl_se);
1271 		goto unlock;
1272 	}
1273 
1274 	if (unlikely(!rq->online)) {
1275 		/*
1276 		 * If the runqueue is no longer available, migrate the
1277 		 * task elsewhere. This necessarily changes rq.
1278 		 */
1279 		lockdep_unpin_lock(__rq_lockp(rq), rf.cookie);
1280 		rq = dl_task_offline_migration(rq, p);
1281 		rf.cookie = lockdep_pin_lock(__rq_lockp(rq));
1282 		update_rq_clock(rq);
1283 
1284 		/*
1285 		 * Now that the task has been migrated to the new RQ and we
1286 		 * have that locked, proceed as normal and enqueue the task
1287 		 * there.
1288 		 */
1289 	}
1290 
1291 	enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
1292 	if (dl_task(rq->donor))
1293 		wakeup_preempt_dl(rq, p, 0);
1294 	else
1295 		resched_curr(rq);
1296 
1297 	__push_dl_task(rq, &rf);
1298 
1299 unlock:
1300 	task_rq_unlock(rq, p, &rf);
1301 
1302 	/*
1303 	 * This can free the task_struct, including this hrtimer, do not touch
1304 	 * anything related to that after this.
1305 	 */
1306 	put_task_struct(p);
1307 
1308 	return HRTIMER_NORESTART;
1309 }
1310 
init_dl_task_timer(struct sched_dl_entity * dl_se)1311 static void init_dl_task_timer(struct sched_dl_entity *dl_se)
1312 {
1313 	struct hrtimer *timer = &dl_se->dl_timer;
1314 
1315 	hrtimer_setup(timer, dl_task_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
1316 }
1317 
1318 /*
1319  * During the activation, CBS checks if it can reuse the current task's
1320  * runtime and period. If the deadline of the task is in the past, CBS
1321  * cannot use the runtime, and so it replenishes the task. This rule
1322  * works fine for implicit deadline tasks (deadline == period), and the
1323  * CBS was designed for implicit deadline tasks. However, a task with
1324  * constrained deadline (deadline < period) might be awakened after the
1325  * deadline, but before the next period. In this case, replenishing the
1326  * task would allow it to run for runtime / deadline. As in this case
1327  * deadline < period, CBS enables a task to run for more than the
1328  * runtime / period. In a very loaded system, this can cause a domino
1329  * effect, making other tasks miss their deadlines.
1330  *
1331  * To avoid this problem, in the activation of a constrained deadline
1332  * task after the deadline but before the next period, throttle the
1333  * task and set the replenishing timer to the begin of the next period,
1334  * unless it is boosted.
1335  */
dl_check_constrained_dl(struct sched_dl_entity * dl_se)1336 static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
1337 {
1338 	struct rq *rq = rq_of_dl_se(dl_se);
1339 
1340 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
1341 	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
1342 		if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(dl_se)))
1343 			return;
1344 		dl_se->dl_throttled = 1;
1345 		if (dl_se->runtime > 0)
1346 			dl_se->runtime = 0;
1347 	}
1348 }
1349 
1350 static
dl_runtime_exceeded(struct sched_dl_entity * dl_se)1351 int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
1352 {
1353 	return (dl_se->runtime <= 0);
1354 }
1355 
1356 /*
1357  * This function implements the GRUB accounting rule. According to the
1358  * GRUB reclaiming algorithm, the runtime is not decreased as "dq = -dt",
1359  * but as "dq = -(max{u, (Umax - Uinact - Uextra)} / Umax) dt",
1360  * where u is the utilization of the task, Umax is the maximum reclaimable
1361  * utilization, Uinact is the (per-runqueue) inactive utilization, computed
1362  * as the difference between the "total runqueue utilization" and the
1363  * "runqueue active utilization", and Uextra is the (per runqueue) extra
1364  * reclaimable utilization.
1365  * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations multiplied
1366  * by 2^BW_SHIFT, the result has to be shifted right by BW_SHIFT.
1367  * Since rq->dl.bw_ratio contains 1 / Umax multiplied by 2^RATIO_SHIFT, dl_bw
1368  * is multiplied by rq->dl.bw_ratio and shifted right by RATIO_SHIFT.
1369  * Since delta is a 64 bit variable, to have an overflow its value should be
1370  * larger than 2^(64 - 20 - 8), which is more than 64 seconds. So, overflow is
1371  * not an issue here.
1372  */
grub_reclaim(u64 delta,struct rq * rq,struct sched_dl_entity * dl_se)1373 static u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity *dl_se)
1374 {
1375 	u64 u_act;
1376 	u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot - Uact */
1377 
1378 	/*
1379 	 * Instead of computing max{u, (u_max - u_inact - u_extra)}, we
1380 	 * compare u_inact + u_extra with u_max - u, because u_inact + u_extra
1381 	 * can be larger than u_max. So, u_max - u_inact - u_extra would be
1382 	 * negative leading to wrong results.
1383 	 */
1384 	if (u_inact + rq->dl.extra_bw > rq->dl.max_bw - dl_se->dl_bw)
1385 		u_act = dl_se->dl_bw;
1386 	else
1387 		u_act = rq->dl.max_bw - u_inact - rq->dl.extra_bw;
1388 
1389 	u_act = (u_act * rq->dl.bw_ratio) >> RATIO_SHIFT;
1390 	return (delta * u_act) >> BW_SHIFT;
1391 }
1392 
dl_scaled_delta_exec(struct rq * rq,struct sched_dl_entity * dl_se,s64 delta_exec)1393 s64 dl_scaled_delta_exec(struct rq *rq, struct sched_dl_entity *dl_se, s64 delta_exec)
1394 {
1395 	s64 scaled_delta_exec;
1396 
1397 	/*
1398 	 * For tasks that participate in GRUB, we implement GRUB-PA: the
1399 	 * spare reclaimed bandwidth is used to clock down frequency.
1400 	 *
1401 	 * For the others, we still need to scale reservation parameters
1402 	 * according to current frequency and CPU maximum capacity.
1403 	 */
1404 	if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) {
1405 		scaled_delta_exec = grub_reclaim(delta_exec, rq, dl_se);
1406 	} else {
1407 		int cpu = cpu_of(rq);
1408 		unsigned long scale_freq = arch_scale_freq_capacity(cpu);
1409 		unsigned long scale_cpu = arch_scale_cpu_capacity(cpu);
1410 
1411 		scaled_delta_exec = cap_scale(delta_exec, scale_freq);
1412 		scaled_delta_exec = cap_scale(scaled_delta_exec, scale_cpu);
1413 	}
1414 
1415 	return scaled_delta_exec;
1416 }
1417 
1418 static inline void
1419 update_stats_dequeue_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se,
1420 			int flags);
update_curr_dl_se(struct rq * rq,struct sched_dl_entity * dl_se,s64 delta_exec)1421 static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64 delta_exec)
1422 {
1423 	s64 scaled_delta_exec;
1424 
1425 	if (unlikely(delta_exec <= 0)) {
1426 		if (unlikely(dl_se->dl_yielded))
1427 			goto throttle;
1428 		return;
1429 	}
1430 
1431 	if (dl_server(dl_se) && dl_se->dl_throttled && !dl_se->dl_defer)
1432 		return;
1433 
1434 	if (dl_entity_is_special(dl_se))
1435 		return;
1436 
1437 	scaled_delta_exec = delta_exec;
1438 	if (!dl_server(dl_se))
1439 		scaled_delta_exec = dl_scaled_delta_exec(rq, dl_se, delta_exec);
1440 
1441 	dl_se->runtime -= scaled_delta_exec;
1442 
1443 	/*
1444 	 * The fair server can consume its runtime while throttled (not queued/
1445 	 * running as regular CFS).
1446 	 *
1447 	 * If the server consumes its entire runtime in this state. The server
1448 	 * is not required for the current period. Thus, reset the server by
1449 	 * starting a new period, pushing the activation.
1450 	 */
1451 	if (dl_se->dl_defer && dl_se->dl_throttled && dl_runtime_exceeded(dl_se)) {
1452 		/*
1453 		 * If the server was previously activated - the starving condition
1454 		 * took place, it this point it went away because the fair scheduler
1455 		 * was able to get runtime in background. So return to the initial
1456 		 * state.
1457 		 */
1458 		dl_se->dl_defer_running = 0;
1459 
1460 		hrtimer_try_to_cancel(&dl_se->dl_timer);
1461 
1462 		replenish_dl_new_period(dl_se, dl_se->rq);
1463 
1464 		/*
1465 		 * Not being able to start the timer seems problematic. If it could not
1466 		 * be started for whatever reason, we need to "unthrottle" the DL server
1467 		 * and queue right away. Otherwise nothing might queue it. That's similar
1468 		 * to what enqueue_dl_entity() does on start_dl_timer==0. For now, just warn.
1469 		 */
1470 		WARN_ON_ONCE(!start_dl_timer(dl_se));
1471 
1472 		return;
1473 	}
1474 
1475 throttle:
1476 	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
1477 		dl_se->dl_throttled = 1;
1478 
1479 		/* If requested, inform the user about runtime overruns. */
1480 		if (dl_runtime_exceeded(dl_se) &&
1481 		    (dl_se->flags & SCHED_FLAG_DL_OVERRUN))
1482 			dl_se->dl_overrun = 1;
1483 
1484 		dequeue_dl_entity(dl_se, 0);
1485 		if (!dl_server(dl_se)) {
1486 			update_stats_dequeue_dl(&rq->dl, dl_se, 0);
1487 			dequeue_pushable_dl_task(rq, dl_task_of(dl_se));
1488 		}
1489 
1490 		if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(dl_se))) {
1491 			if (dl_server(dl_se)) {
1492 				replenish_dl_new_period(dl_se, rq);
1493 				start_dl_timer(dl_se);
1494 			} else {
1495 				enqueue_task_dl(rq, dl_task_of(dl_se), ENQUEUE_REPLENISH);
1496 			}
1497 		}
1498 
1499 		if (!is_leftmost(dl_se, &rq->dl))
1500 			resched_curr(rq);
1501 	}
1502 
1503 	/*
1504 	 * The fair server (sole dl_server) does not account for real-time
1505 	 * workload because it is running fair work.
1506 	 */
1507 	if (dl_se == &rq->fair_server)
1508 		return;
1509 
1510 #ifdef CONFIG_RT_GROUP_SCHED
1511 	/*
1512 	 * Because -- for now -- we share the rt bandwidth, we need to
1513 	 * account our runtime there too, otherwise actual rt tasks
1514 	 * would be able to exceed the shared quota.
1515 	 *
1516 	 * Account to the root rt group for now.
1517 	 *
1518 	 * The solution we're working towards is having the RT groups scheduled
1519 	 * using deadline servers -- however there's a few nasties to figure
1520 	 * out before that can happen.
1521 	 */
1522 	if (rt_bandwidth_enabled()) {
1523 		struct rt_rq *rt_rq = &rq->rt;
1524 
1525 		raw_spin_lock(&rt_rq->rt_runtime_lock);
1526 		/*
1527 		 * We'll let actual RT tasks worry about the overflow here, we
1528 		 * have our own CBS to keep us inline; only account when RT
1529 		 * bandwidth is relevant.
1530 		 */
1531 		if (sched_rt_bandwidth_account(rt_rq))
1532 			rt_rq->rt_time += delta_exec;
1533 		raw_spin_unlock(&rt_rq->rt_runtime_lock);
1534 	}
1535 #endif /* CONFIG_RT_GROUP_SCHED */
1536 }
1537 
1538 /*
1539  * In the non-defer mode, the idle time is not accounted, as the
1540  * server provides a guarantee.
1541  *
1542  * If the dl_server is in defer mode, the idle time is also considered
1543  * as time available for the fair server, avoiding a penalty for the
1544  * rt scheduler that did not consumed that time.
1545  */
dl_server_update_idle_time(struct rq * rq,struct task_struct * p)1546 void dl_server_update_idle_time(struct rq *rq, struct task_struct *p)
1547 {
1548 	s64 delta_exec;
1549 
1550 	if (!rq->fair_server.dl_defer)
1551 		return;
1552 
1553 	/* no need to discount more */
1554 	if (rq->fair_server.runtime < 0)
1555 		return;
1556 
1557 	delta_exec = rq_clock_task(rq) - p->se.exec_start;
1558 	if (delta_exec < 0)
1559 		return;
1560 
1561 	rq->fair_server.runtime -= delta_exec;
1562 
1563 	if (rq->fair_server.runtime < 0) {
1564 		rq->fair_server.dl_defer_running = 0;
1565 		rq->fair_server.runtime = 0;
1566 	}
1567 
1568 	p->se.exec_start = rq_clock_task(rq);
1569 }
1570 
dl_server_update(struct sched_dl_entity * dl_se,s64 delta_exec)1571 void dl_server_update(struct sched_dl_entity *dl_se, s64 delta_exec)
1572 {
1573 	/* 0 runtime = fair server disabled */
1574 	if (dl_se->dl_runtime)
1575 		update_curr_dl_se(dl_se->rq, dl_se, delta_exec);
1576 }
1577 
dl_server_start(struct sched_dl_entity * dl_se)1578 void dl_server_start(struct sched_dl_entity *dl_se)
1579 {
1580 	struct rq *rq = dl_se->rq;
1581 
1582 	if (!dl_server(dl_se) || dl_se->dl_server_active)
1583 		return;
1584 
1585 	if (WARN_ON_ONCE(!cpu_online(cpu_of(rq))))
1586 		return;
1587 
1588 	dl_se->dl_server_active = 1;
1589 	enqueue_dl_entity(dl_se, ENQUEUE_WAKEUP);
1590 	if (!dl_task(dl_se->rq->curr) || dl_entity_preempt(dl_se, &rq->curr->dl))
1591 		resched_curr(dl_se->rq);
1592 }
1593 
dl_server_stop(struct sched_dl_entity * dl_se)1594 void dl_server_stop(struct sched_dl_entity *dl_se)
1595 {
1596 	if (!dl_server(dl_se) || !dl_server_active(dl_se))
1597 		return;
1598 
1599 	dequeue_dl_entity(dl_se, DEQUEUE_SLEEP);
1600 	hrtimer_try_to_cancel(&dl_se->dl_timer);
1601 	dl_se->dl_defer_armed = 0;
1602 	dl_se->dl_throttled = 0;
1603 	dl_se->dl_server_active = 0;
1604 }
1605 
dl_server_init(struct sched_dl_entity * dl_se,struct rq * rq,dl_server_pick_f pick_task)1606 void dl_server_init(struct sched_dl_entity *dl_se, struct rq *rq,
1607 		    dl_server_pick_f pick_task)
1608 {
1609 	dl_se->rq = rq;
1610 	dl_se->server_pick_task = pick_task;
1611 }
1612 
sched_init_dl_servers(void)1613 void sched_init_dl_servers(void)
1614 {
1615 	int cpu;
1616 	struct rq *rq;
1617 	struct sched_dl_entity *dl_se;
1618 
1619 	for_each_online_cpu(cpu) {
1620 		u64 runtime =  50 * NSEC_PER_MSEC;
1621 		u64 period = 1000 * NSEC_PER_MSEC;
1622 
1623 		rq = cpu_rq(cpu);
1624 
1625 		guard(rq_lock_irq)(rq);
1626 
1627 		dl_se = &rq->fair_server;
1628 
1629 		WARN_ON(dl_server(dl_se));
1630 
1631 		dl_server_apply_params(dl_se, runtime, period, 1);
1632 
1633 		dl_se->dl_server = 1;
1634 		dl_se->dl_defer = 1;
1635 		setup_new_dl_entity(dl_se);
1636 	}
1637 }
1638 
__dl_server_attach_root(struct sched_dl_entity * dl_se,struct rq * rq)1639 void __dl_server_attach_root(struct sched_dl_entity *dl_se, struct rq *rq)
1640 {
1641 	u64 new_bw = dl_se->dl_bw;
1642 	int cpu = cpu_of(rq);
1643 	struct dl_bw *dl_b;
1644 
1645 	dl_b = dl_bw_of(cpu_of(rq));
1646 	guard(raw_spinlock)(&dl_b->lock);
1647 
1648 	if (!dl_bw_cpus(cpu))
1649 		return;
1650 
1651 	__dl_add(dl_b, new_bw, dl_bw_cpus(cpu));
1652 }
1653 
dl_server_apply_params(struct sched_dl_entity * dl_se,u64 runtime,u64 period,bool init)1654 int dl_server_apply_params(struct sched_dl_entity *dl_se, u64 runtime, u64 period, bool init)
1655 {
1656 	u64 old_bw = init ? 0 : to_ratio(dl_se->dl_period, dl_se->dl_runtime);
1657 	u64 new_bw = to_ratio(period, runtime);
1658 	struct rq *rq = dl_se->rq;
1659 	int cpu = cpu_of(rq);
1660 	struct dl_bw *dl_b;
1661 	unsigned long cap;
1662 	int retval = 0;
1663 	int cpus;
1664 
1665 	dl_b = dl_bw_of(cpu);
1666 	guard(raw_spinlock)(&dl_b->lock);
1667 
1668 	cpus = dl_bw_cpus(cpu);
1669 	cap = dl_bw_capacity(cpu);
1670 
1671 	if (__dl_overflow(dl_b, cap, old_bw, new_bw))
1672 		return -EBUSY;
1673 
1674 	if (init) {
1675 		__add_rq_bw(new_bw, &rq->dl);
1676 		__dl_add(dl_b, new_bw, cpus);
1677 	} else {
1678 		__dl_sub(dl_b, dl_se->dl_bw, cpus);
1679 		__dl_add(dl_b, new_bw, cpus);
1680 
1681 		dl_rq_change_utilization(rq, dl_se, new_bw);
1682 	}
1683 
1684 	dl_se->dl_runtime = runtime;
1685 	dl_se->dl_deadline = period;
1686 	dl_se->dl_period = period;
1687 
1688 	dl_se->runtime = 0;
1689 	dl_se->deadline = 0;
1690 
1691 	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
1692 	dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime);
1693 
1694 	return retval;
1695 }
1696 
1697 /*
1698  * Update the current task's runtime statistics (provided it is still
1699  * a -deadline task and has not been removed from the dl_rq).
1700  */
update_curr_dl(struct rq * rq)1701 static void update_curr_dl(struct rq *rq)
1702 {
1703 	struct task_struct *donor = rq->donor;
1704 	struct sched_dl_entity *dl_se = &donor->dl;
1705 	s64 delta_exec;
1706 
1707 	if (!dl_task(donor) || !on_dl_rq(dl_se))
1708 		return;
1709 
1710 	/*
1711 	 * Consumed budget is computed considering the time as
1712 	 * observed by schedulable tasks (excluding time spent
1713 	 * in hardirq context, etc.). Deadlines are instead
1714 	 * computed using hard walltime. This seems to be the more
1715 	 * natural solution, but the full ramifications of this
1716 	 * approach need further study.
1717 	 */
1718 	delta_exec = update_curr_common(rq);
1719 	update_curr_dl_se(rq, dl_se, delta_exec);
1720 }
1721 
inactive_task_timer(struct hrtimer * timer)1722 static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
1723 {
1724 	struct sched_dl_entity *dl_se = container_of(timer,
1725 						     struct sched_dl_entity,
1726 						     inactive_timer);
1727 	struct task_struct *p = NULL;
1728 	struct rq_flags rf;
1729 	struct rq *rq;
1730 
1731 	if (!dl_server(dl_se)) {
1732 		p = dl_task_of(dl_se);
1733 		rq = task_rq_lock(p, &rf);
1734 	} else {
1735 		rq = dl_se->rq;
1736 		rq_lock(rq, &rf);
1737 	}
1738 
1739 	sched_clock_tick();
1740 	update_rq_clock(rq);
1741 
1742 	if (dl_server(dl_se))
1743 		goto no_task;
1744 
1745 	if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) {
1746 		struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
1747 
1748 		if (READ_ONCE(p->__state) == TASK_DEAD && dl_se->dl_non_contending) {
1749 			sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
1750 			sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl));
1751 			dl_se->dl_non_contending = 0;
1752 		}
1753 
1754 		raw_spin_lock(&dl_b->lock);
1755 		__dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
1756 		raw_spin_unlock(&dl_b->lock);
1757 		__dl_clear_params(dl_se);
1758 
1759 		goto unlock;
1760 	}
1761 
1762 no_task:
1763 	if (dl_se->dl_non_contending == 0)
1764 		goto unlock;
1765 
1766 	sub_running_bw(dl_se, &rq->dl);
1767 	dl_se->dl_non_contending = 0;
1768 unlock:
1769 
1770 	if (!dl_server(dl_se)) {
1771 		task_rq_unlock(rq, p, &rf);
1772 		put_task_struct(p);
1773 	} else {
1774 		rq_unlock(rq, &rf);
1775 	}
1776 
1777 	return HRTIMER_NORESTART;
1778 }
1779 
init_dl_inactive_task_timer(struct sched_dl_entity * dl_se)1780 static void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se)
1781 {
1782 	struct hrtimer *timer = &dl_se->inactive_timer;
1783 
1784 	hrtimer_setup(timer, inactive_task_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
1785 }
1786 
1787 #define __node_2_dle(node) \
1788 	rb_entry((node), struct sched_dl_entity, rb_node)
1789 
inc_dl_deadline(struct dl_rq * dl_rq,u64 deadline)1790 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
1791 {
1792 	struct rq *rq = rq_of_dl_rq(dl_rq);
1793 
1794 	if (dl_rq->earliest_dl.curr == 0 ||
1795 	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
1796 		if (dl_rq->earliest_dl.curr == 0)
1797 			cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_HIGHER);
1798 		dl_rq->earliest_dl.curr = deadline;
1799 		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline);
1800 	}
1801 }
1802 
dec_dl_deadline(struct dl_rq * dl_rq,u64 deadline)1803 static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
1804 {
1805 	struct rq *rq = rq_of_dl_rq(dl_rq);
1806 
1807 	/*
1808 	 * Since we may have removed our earliest (and/or next earliest)
1809 	 * task we must recompute them.
1810 	 */
1811 	if (!dl_rq->dl_nr_running) {
1812 		dl_rq->earliest_dl.curr = 0;
1813 		dl_rq->earliest_dl.next = 0;
1814 		cpudl_clear(&rq->rd->cpudl, rq->cpu);
1815 		cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
1816 	} else {
1817 		struct rb_node *leftmost = rb_first_cached(&dl_rq->root);
1818 		struct sched_dl_entity *entry = __node_2_dle(leftmost);
1819 
1820 		dl_rq->earliest_dl.curr = entry->deadline;
1821 		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline);
1822 	}
1823 }
1824 
1825 static inline
inc_dl_tasks(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)1826 void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
1827 {
1828 	u64 deadline = dl_se->deadline;
1829 
1830 	dl_rq->dl_nr_running++;
1831 
1832 	if (!dl_server(dl_se))
1833 		add_nr_running(rq_of_dl_rq(dl_rq), 1);
1834 
1835 	inc_dl_deadline(dl_rq, deadline);
1836 }
1837 
1838 static inline
dec_dl_tasks(struct sched_dl_entity * dl_se,struct dl_rq * dl_rq)1839 void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
1840 {
1841 	WARN_ON(!dl_rq->dl_nr_running);
1842 	dl_rq->dl_nr_running--;
1843 
1844 	if (!dl_server(dl_se))
1845 		sub_nr_running(rq_of_dl_rq(dl_rq), 1);
1846 
1847 	dec_dl_deadline(dl_rq, dl_se->deadline);
1848 }
1849 
__dl_less(struct rb_node * a,const struct rb_node * b)1850 static inline bool __dl_less(struct rb_node *a, const struct rb_node *b)
1851 {
1852 	return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline);
1853 }
1854 
1855 static __always_inline struct sched_statistics *
__schedstats_from_dl_se(struct sched_dl_entity * dl_se)1856 __schedstats_from_dl_se(struct sched_dl_entity *dl_se)
1857 {
1858 	if (!schedstat_enabled())
1859 		return NULL;
1860 
1861 	if (dl_server(dl_se))
1862 		return NULL;
1863 
1864 	return &dl_task_of(dl_se)->stats;
1865 }
1866 
1867 static inline void
update_stats_wait_start_dl(struct dl_rq * dl_rq,struct sched_dl_entity * dl_se)1868 update_stats_wait_start_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se)
1869 {
1870 	struct sched_statistics *stats = __schedstats_from_dl_se(dl_se);
1871 	if (stats)
1872 		__update_stats_wait_start(rq_of_dl_rq(dl_rq), dl_task_of(dl_se), stats);
1873 }
1874 
1875 static inline void
update_stats_wait_end_dl(struct dl_rq * dl_rq,struct sched_dl_entity * dl_se)1876 update_stats_wait_end_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se)
1877 {
1878 	struct sched_statistics *stats = __schedstats_from_dl_se(dl_se);
1879 	if (stats)
1880 		__update_stats_wait_end(rq_of_dl_rq(dl_rq), dl_task_of(dl_se), stats);
1881 }
1882 
1883 static inline void
update_stats_enqueue_sleeper_dl(struct dl_rq * dl_rq,struct sched_dl_entity * dl_se)1884 update_stats_enqueue_sleeper_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se)
1885 {
1886 	struct sched_statistics *stats = __schedstats_from_dl_se(dl_se);
1887 	if (stats)
1888 		__update_stats_enqueue_sleeper(rq_of_dl_rq(dl_rq), dl_task_of(dl_se), stats);
1889 }
1890 
1891 static inline void
update_stats_enqueue_dl(struct dl_rq * dl_rq,struct sched_dl_entity * dl_se,int flags)1892 update_stats_enqueue_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se,
1893 			int flags)
1894 {
1895 	if (!schedstat_enabled())
1896 		return;
1897 
1898 	if (flags & ENQUEUE_WAKEUP)
1899 		update_stats_enqueue_sleeper_dl(dl_rq, dl_se);
1900 }
1901 
1902 static inline void
update_stats_dequeue_dl(struct dl_rq * dl_rq,struct sched_dl_entity * dl_se,int flags)1903 update_stats_dequeue_dl(struct dl_rq *dl_rq, struct sched_dl_entity *dl_se,
1904 			int flags)
1905 {
1906 	struct task_struct *p = dl_task_of(dl_se);
1907 
1908 	if (!schedstat_enabled())
1909 		return;
1910 
1911 	if ((flags & DEQUEUE_SLEEP)) {
1912 		unsigned int state;
1913 
1914 		state = READ_ONCE(p->__state);
1915 		if (state & TASK_INTERRUPTIBLE)
1916 			__schedstat_set(p->stats.sleep_start,
1917 					rq_clock(rq_of_dl_rq(dl_rq)));
1918 
1919 		if (state & TASK_UNINTERRUPTIBLE)
1920 			__schedstat_set(p->stats.block_start,
1921 					rq_clock(rq_of_dl_rq(dl_rq)));
1922 	}
1923 }
1924 
__enqueue_dl_entity(struct sched_dl_entity * dl_se)1925 static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
1926 {
1927 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1928 
1929 	WARN_ON_ONCE(!RB_EMPTY_NODE(&dl_se->rb_node));
1930 
1931 	rb_add_cached(&dl_se->rb_node, &dl_rq->root, __dl_less);
1932 
1933 	inc_dl_tasks(dl_se, dl_rq);
1934 }
1935 
__dequeue_dl_entity(struct sched_dl_entity * dl_se)1936 static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
1937 {
1938 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1939 
1940 	if (RB_EMPTY_NODE(&dl_se->rb_node))
1941 		return;
1942 
1943 	rb_erase_cached(&dl_se->rb_node, &dl_rq->root);
1944 
1945 	RB_CLEAR_NODE(&dl_se->rb_node);
1946 
1947 	dec_dl_tasks(dl_se, dl_rq);
1948 }
1949 
1950 static void
enqueue_dl_entity(struct sched_dl_entity * dl_se,int flags)1951 enqueue_dl_entity(struct sched_dl_entity *dl_se, int flags)
1952 {
1953 	WARN_ON_ONCE(on_dl_rq(dl_se));
1954 
1955 	update_stats_enqueue_dl(dl_rq_of_se(dl_se), dl_se, flags);
1956 
1957 	/*
1958 	 * Check if a constrained deadline task was activated
1959 	 * after the deadline but before the next period.
1960 	 * If that is the case, the task will be throttled and
1961 	 * the replenishment timer will be set to the next period.
1962 	 */
1963 	if (!dl_se->dl_throttled && !dl_is_implicit(dl_se))
1964 		dl_check_constrained_dl(dl_se);
1965 
1966 	if (flags & (ENQUEUE_RESTORE|ENQUEUE_MIGRATING)) {
1967 		struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1968 
1969 		add_rq_bw(dl_se, dl_rq);
1970 		add_running_bw(dl_se, dl_rq);
1971 	}
1972 
1973 	/*
1974 	 * If p is throttled, we do not enqueue it. In fact, if it exhausted
1975 	 * its budget it needs a replenishment and, since it now is on
1976 	 * its rq, the bandwidth timer callback (which clearly has not
1977 	 * run yet) will take care of this.
1978 	 * However, the active utilization does not depend on the fact
1979 	 * that the task is on the runqueue or not (but depends on the
1980 	 * task's state - in GRUB parlance, "inactive" vs "active contending").
1981 	 * In other words, even if a task is throttled its utilization must
1982 	 * be counted in the active utilization; hence, we need to call
1983 	 * add_running_bw().
1984 	 */
1985 	if (!dl_se->dl_defer && dl_se->dl_throttled && !(flags & ENQUEUE_REPLENISH)) {
1986 		if (flags & ENQUEUE_WAKEUP)
1987 			task_contending(dl_se, flags);
1988 
1989 		return;
1990 	}
1991 
1992 	/*
1993 	 * If this is a wakeup or a new instance, the scheduling
1994 	 * parameters of the task might need updating. Otherwise,
1995 	 * we want a replenishment of its runtime.
1996 	 */
1997 	if (flags & ENQUEUE_WAKEUP) {
1998 		task_contending(dl_se, flags);
1999 		update_dl_entity(dl_se);
2000 	} else if (flags & ENQUEUE_REPLENISH) {
2001 		replenish_dl_entity(dl_se);
2002 	} else if ((flags & ENQUEUE_RESTORE) &&
2003 		   !is_dl_boosted(dl_se) &&
2004 		   dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) {
2005 		setup_new_dl_entity(dl_se);
2006 	}
2007 
2008 	/*
2009 	 * If the reservation is still throttled, e.g., it got replenished but is a
2010 	 * deferred task and still got to wait, don't enqueue.
2011 	 */
2012 	if (dl_se->dl_throttled && start_dl_timer(dl_se))
2013 		return;
2014 
2015 	/*
2016 	 * We're about to enqueue, make sure we're not ->dl_throttled!
2017 	 * In case the timer was not started, say because the defer time
2018 	 * has passed, mark as not throttled and mark unarmed.
2019 	 * Also cancel earlier timers, since letting those run is pointless.
2020 	 */
2021 	if (dl_se->dl_throttled) {
2022 		hrtimer_try_to_cancel(&dl_se->dl_timer);
2023 		dl_se->dl_defer_armed = 0;
2024 		dl_se->dl_throttled = 0;
2025 	}
2026 
2027 	__enqueue_dl_entity(dl_se);
2028 }
2029 
dequeue_dl_entity(struct sched_dl_entity * dl_se,int flags)2030 static void dequeue_dl_entity(struct sched_dl_entity *dl_se, int flags)
2031 {
2032 	__dequeue_dl_entity(dl_se);
2033 
2034 	if (flags & (DEQUEUE_SAVE|DEQUEUE_MIGRATING)) {
2035 		struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
2036 
2037 		sub_running_bw(dl_se, dl_rq);
2038 		sub_rq_bw(dl_se, dl_rq);
2039 	}
2040 
2041 	/*
2042 	 * This check allows to start the inactive timer (or to immediately
2043 	 * decrease the active utilization, if needed) in two cases:
2044 	 * when the task blocks and when it is terminating
2045 	 * (p->state == TASK_DEAD). We can handle the two cases in the same
2046 	 * way, because from GRUB's point of view the same thing is happening
2047 	 * (the task moves from "active contending" to "active non contending"
2048 	 * or "inactive")
2049 	 */
2050 	if (flags & DEQUEUE_SLEEP)
2051 		task_non_contending(dl_se);
2052 }
2053 
enqueue_task_dl(struct rq * rq,struct task_struct * p,int flags)2054 static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
2055 {
2056 	if (is_dl_boosted(&p->dl)) {
2057 		/*
2058 		 * Because of delays in the detection of the overrun of a
2059 		 * thread's runtime, it might be the case that a thread
2060 		 * goes to sleep in a rt mutex with negative runtime. As
2061 		 * a consequence, the thread will be throttled.
2062 		 *
2063 		 * While waiting for the mutex, this thread can also be
2064 		 * boosted via PI, resulting in a thread that is throttled
2065 		 * and boosted at the same time.
2066 		 *
2067 		 * In this case, the boost overrides the throttle.
2068 		 */
2069 		if (p->dl.dl_throttled) {
2070 			/*
2071 			 * The replenish timer needs to be canceled. No
2072 			 * problem if it fires concurrently: boosted threads
2073 			 * are ignored in dl_task_timer().
2074 			 */
2075 			cancel_replenish_timer(&p->dl);
2076 			p->dl.dl_throttled = 0;
2077 		}
2078 	} else if (!dl_prio(p->normal_prio)) {
2079 		/*
2080 		 * Special case in which we have a !SCHED_DEADLINE task that is going
2081 		 * to be deboosted, but exceeds its runtime while doing so. No point in
2082 		 * replenishing it, as it's going to return back to its original
2083 		 * scheduling class after this. If it has been throttled, we need to
2084 		 * clear the flag, otherwise the task may wake up as throttled after
2085 		 * being boosted again with no means to replenish the runtime and clear
2086 		 * the throttle.
2087 		 */
2088 		p->dl.dl_throttled = 0;
2089 		if (!(flags & ENQUEUE_REPLENISH))
2090 			printk_deferred_once("sched: DL de-boosted task PID %d: REPLENISH flag missing\n",
2091 					     task_pid_nr(p));
2092 
2093 		return;
2094 	}
2095 
2096 	check_schedstat_required();
2097 	update_stats_wait_start_dl(dl_rq_of_se(&p->dl), &p->dl);
2098 
2099 	if (p->on_rq == TASK_ON_RQ_MIGRATING)
2100 		flags |= ENQUEUE_MIGRATING;
2101 
2102 	enqueue_dl_entity(&p->dl, flags);
2103 
2104 	if (dl_server(&p->dl))
2105 		return;
2106 
2107 	if (task_is_blocked(p))
2108 		return;
2109 
2110 	if (!task_current(rq, p) && !p->dl.dl_throttled && p->nr_cpus_allowed > 1)
2111 		enqueue_pushable_dl_task(rq, p);
2112 }
2113 
dequeue_task_dl(struct rq * rq,struct task_struct * p,int flags)2114 static bool dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
2115 {
2116 	update_curr_dl(rq);
2117 
2118 	if (p->on_rq == TASK_ON_RQ_MIGRATING)
2119 		flags |= DEQUEUE_MIGRATING;
2120 
2121 	dequeue_dl_entity(&p->dl, flags);
2122 	if (!p->dl.dl_throttled && !dl_server(&p->dl))
2123 		dequeue_pushable_dl_task(rq, p);
2124 
2125 	return true;
2126 }
2127 
2128 /*
2129  * Yield task semantic for -deadline tasks is:
2130  *
2131  *   get off from the CPU until our next instance, with
2132  *   a new runtime. This is of little use now, since we
2133  *   don't have a bandwidth reclaiming mechanism. Anyway,
2134  *   bandwidth reclaiming is planned for the future, and
2135  *   yield_task_dl will indicate that some spare budget
2136  *   is available for other task instances to use it.
2137  */
yield_task_dl(struct rq * rq)2138 static void yield_task_dl(struct rq *rq)
2139 {
2140 	/*
2141 	 * We make the task go to sleep until its current deadline by
2142 	 * forcing its runtime to zero. This way, update_curr_dl() stops
2143 	 * it and the bandwidth timer will wake it up and will give it
2144 	 * new scheduling parameters (thanks to dl_yielded=1).
2145 	 */
2146 	rq->curr->dl.dl_yielded = 1;
2147 
2148 	update_rq_clock(rq);
2149 	update_curr_dl(rq);
2150 	/*
2151 	 * Tell update_rq_clock() that we've just updated,
2152 	 * so we don't do microscopic update in schedule()
2153 	 * and double the fastpath cost.
2154 	 */
2155 	rq_clock_skip_update(rq);
2156 }
2157 
dl_task_is_earliest_deadline(struct task_struct * p,struct rq * rq)2158 static inline bool dl_task_is_earliest_deadline(struct task_struct *p,
2159 						 struct rq *rq)
2160 {
2161 	return (!rq->dl.dl_nr_running ||
2162 		dl_time_before(p->dl.deadline,
2163 			       rq->dl.earliest_dl.curr));
2164 }
2165 
2166 static int find_later_rq(struct task_struct *task);
2167 
2168 static int
select_task_rq_dl(struct task_struct * p,int cpu,int flags)2169 select_task_rq_dl(struct task_struct *p, int cpu, int flags)
2170 {
2171 	struct task_struct *curr, *donor;
2172 	bool select_rq;
2173 	struct rq *rq;
2174 
2175 	if (!(flags & WF_TTWU))
2176 		goto out;
2177 
2178 	rq = cpu_rq(cpu);
2179 
2180 	rcu_read_lock();
2181 	curr = READ_ONCE(rq->curr); /* unlocked access */
2182 	donor = READ_ONCE(rq->donor);
2183 
2184 	/*
2185 	 * If we are dealing with a -deadline task, we must
2186 	 * decide where to wake it up.
2187 	 * If it has a later deadline and the current task
2188 	 * on this rq can't move (provided the waking task
2189 	 * can!) we prefer to send it somewhere else. On the
2190 	 * other hand, if it has a shorter deadline, we
2191 	 * try to make it stay here, it might be important.
2192 	 */
2193 	select_rq = unlikely(dl_task(donor)) &&
2194 		    (curr->nr_cpus_allowed < 2 ||
2195 		     !dl_entity_preempt(&p->dl, &donor->dl)) &&
2196 		    p->nr_cpus_allowed > 1;
2197 
2198 	/*
2199 	 * Take the capacity of the CPU into account to
2200 	 * ensure it fits the requirement of the task.
2201 	 */
2202 	if (sched_asym_cpucap_active())
2203 		select_rq |= !dl_task_fits_capacity(p, cpu);
2204 
2205 	if (select_rq) {
2206 		int target = find_later_rq(p);
2207 
2208 		if (target != -1 &&
2209 		    dl_task_is_earliest_deadline(p, cpu_rq(target)))
2210 			cpu = target;
2211 	}
2212 	rcu_read_unlock();
2213 
2214 out:
2215 	return cpu;
2216 }
2217 
migrate_task_rq_dl(struct task_struct * p,int new_cpu __maybe_unused)2218 static void migrate_task_rq_dl(struct task_struct *p, int new_cpu __maybe_unused)
2219 {
2220 	struct rq_flags rf;
2221 	struct rq *rq;
2222 
2223 	if (READ_ONCE(p->__state) != TASK_WAKING)
2224 		return;
2225 
2226 	rq = task_rq(p);
2227 	/*
2228 	 * Since p->state == TASK_WAKING, set_task_cpu() has been called
2229 	 * from try_to_wake_up(). Hence, p->pi_lock is locked, but
2230 	 * rq->lock is not... So, lock it
2231 	 */
2232 	rq_lock(rq, &rf);
2233 	if (p->dl.dl_non_contending) {
2234 		update_rq_clock(rq);
2235 		sub_running_bw(&p->dl, &rq->dl);
2236 		p->dl.dl_non_contending = 0;
2237 		/*
2238 		 * If the timer handler is currently running and the
2239 		 * timer cannot be canceled, inactive_task_timer()
2240 		 * will see that dl_not_contending is not set, and
2241 		 * will not touch the rq's active utilization,
2242 		 * so we are still safe.
2243 		 */
2244 		cancel_inactive_timer(&p->dl);
2245 	}
2246 	sub_rq_bw(&p->dl, &rq->dl);
2247 	rq_unlock(rq, &rf);
2248 }
2249 
check_preempt_equal_dl(struct rq * rq,struct task_struct * p)2250 static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
2251 {
2252 	/*
2253 	 * Current can't be migrated, useless to reschedule,
2254 	 * let's hope p can move out.
2255 	 */
2256 	if (rq->curr->nr_cpus_allowed == 1 ||
2257 	    !cpudl_find(&rq->rd->cpudl, rq->donor, NULL))
2258 		return;
2259 
2260 	/*
2261 	 * p is migratable, so let's not schedule it and
2262 	 * see if it is pushed or pulled somewhere else.
2263 	 */
2264 	if (p->nr_cpus_allowed != 1 &&
2265 	    cpudl_find(&rq->rd->cpudl, p, NULL))
2266 		return;
2267 
2268 	resched_curr(rq);
2269 }
2270 
balance_dl(struct rq * rq,struct task_struct * p,struct rq_flags * rf)2271 static int balance_dl(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
2272 {
2273 	if (!on_dl_rq(&p->dl) && need_pull_dl_task(rq, p)) {
2274 		/*
2275 		 * This is OK, because current is on_cpu, which avoids it being
2276 		 * picked for load-balance and preemption/IRQs are still
2277 		 * disabled avoiding further scheduler activity on it and we've
2278 		 * not yet started the picking loop.
2279 		 */
2280 		rq_unpin_lock(rq, rf);
2281 		pull_dl_task(rq);
2282 		rq_repin_lock(rq, rf);
2283 	}
2284 
2285 	return sched_stop_runnable(rq) || sched_dl_runnable(rq);
2286 }
2287 
2288 /*
2289  * Only called when both the current and waking task are -deadline
2290  * tasks.
2291  */
wakeup_preempt_dl(struct rq * rq,struct task_struct * p,int flags)2292 static void wakeup_preempt_dl(struct rq *rq, struct task_struct *p,
2293 				  int flags)
2294 {
2295 	if (dl_entity_preempt(&p->dl, &rq->donor->dl)) {
2296 		resched_curr(rq);
2297 		return;
2298 	}
2299 
2300 	/*
2301 	 * In the unlikely case current and p have the same deadline
2302 	 * let us try to decide what's the best thing to do...
2303 	 */
2304 	if ((p->dl.deadline == rq->donor->dl.deadline) &&
2305 	    !test_tsk_need_resched(rq->curr))
2306 		check_preempt_equal_dl(rq, p);
2307 }
2308 
2309 #ifdef CONFIG_SCHED_HRTICK
start_hrtick_dl(struct rq * rq,struct sched_dl_entity * dl_se)2310 static void start_hrtick_dl(struct rq *rq, struct sched_dl_entity *dl_se)
2311 {
2312 	hrtick_start(rq, dl_se->runtime);
2313 }
2314 #else /* !CONFIG_SCHED_HRTICK: */
start_hrtick_dl(struct rq * rq,struct sched_dl_entity * dl_se)2315 static void start_hrtick_dl(struct rq *rq, struct sched_dl_entity *dl_se)
2316 {
2317 }
2318 #endif /* !CONFIG_SCHED_HRTICK */
2319 
set_next_task_dl(struct rq * rq,struct task_struct * p,bool first)2320 static void set_next_task_dl(struct rq *rq, struct task_struct *p, bool first)
2321 {
2322 	struct sched_dl_entity *dl_se = &p->dl;
2323 	struct dl_rq *dl_rq = &rq->dl;
2324 
2325 	p->se.exec_start = rq_clock_task(rq);
2326 	if (on_dl_rq(&p->dl))
2327 		update_stats_wait_end_dl(dl_rq, dl_se);
2328 
2329 	/* You can't push away the running task */
2330 	dequeue_pushable_dl_task(rq, p);
2331 
2332 	if (!first)
2333 		return;
2334 
2335 	if (rq->donor->sched_class != &dl_sched_class)
2336 		update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
2337 
2338 	deadline_queue_push_tasks(rq);
2339 
2340 	if (hrtick_enabled_dl(rq))
2341 		start_hrtick_dl(rq, &p->dl);
2342 }
2343 
pick_next_dl_entity(struct dl_rq * dl_rq)2344 static struct sched_dl_entity *pick_next_dl_entity(struct dl_rq *dl_rq)
2345 {
2346 	struct rb_node *left = rb_first_cached(&dl_rq->root);
2347 
2348 	if (!left)
2349 		return NULL;
2350 
2351 	return __node_2_dle(left);
2352 }
2353 
2354 /*
2355  * __pick_next_task_dl - Helper to pick the next -deadline task to run.
2356  * @rq: The runqueue to pick the next task from.
2357  */
__pick_task_dl(struct rq * rq)2358 static struct task_struct *__pick_task_dl(struct rq *rq)
2359 {
2360 	struct sched_dl_entity *dl_se;
2361 	struct dl_rq *dl_rq = &rq->dl;
2362 	struct task_struct *p;
2363 
2364 again:
2365 	if (!sched_dl_runnable(rq))
2366 		return NULL;
2367 
2368 	dl_se = pick_next_dl_entity(dl_rq);
2369 	WARN_ON_ONCE(!dl_se);
2370 
2371 	if (dl_server(dl_se)) {
2372 		p = dl_se->server_pick_task(dl_se);
2373 		if (!p) {
2374 			dl_server_stop(dl_se);
2375 			goto again;
2376 		}
2377 		rq->dl_server = dl_se;
2378 	} else {
2379 		p = dl_task_of(dl_se);
2380 	}
2381 
2382 	return p;
2383 }
2384 
pick_task_dl(struct rq * rq)2385 static struct task_struct *pick_task_dl(struct rq *rq)
2386 {
2387 	return __pick_task_dl(rq);
2388 }
2389 
put_prev_task_dl(struct rq * rq,struct task_struct * p,struct task_struct * next)2390 static void put_prev_task_dl(struct rq *rq, struct task_struct *p, struct task_struct *next)
2391 {
2392 	struct sched_dl_entity *dl_se = &p->dl;
2393 	struct dl_rq *dl_rq = &rq->dl;
2394 
2395 	if (on_dl_rq(&p->dl))
2396 		update_stats_wait_start_dl(dl_rq, dl_se);
2397 
2398 	update_curr_dl(rq);
2399 
2400 	update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
2401 
2402 	if (task_is_blocked(p))
2403 		return;
2404 
2405 	if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1)
2406 		enqueue_pushable_dl_task(rq, p);
2407 }
2408 
2409 /*
2410  * scheduler tick hitting a task of our scheduling class.
2411  *
2412  * NOTE: This function can be called remotely by the tick offload that
2413  * goes along full dynticks. Therefore no local assumption can be made
2414  * and everything must be accessed through the @rq and @curr passed in
2415  * parameters.
2416  */
task_tick_dl(struct rq * rq,struct task_struct * p,int queued)2417 static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
2418 {
2419 	update_curr_dl(rq);
2420 
2421 	update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 1);
2422 	/*
2423 	 * Even when we have runtime, update_curr_dl() might have resulted in us
2424 	 * not being the leftmost task anymore. In that case NEED_RESCHED will
2425 	 * be set and schedule() will start a new hrtick for the next task.
2426 	 */
2427 	if (hrtick_enabled_dl(rq) && queued && p->dl.runtime > 0 &&
2428 	    is_leftmost(&p->dl, &rq->dl))
2429 		start_hrtick_dl(rq, &p->dl);
2430 }
2431 
task_fork_dl(struct task_struct * p)2432 static void task_fork_dl(struct task_struct *p)
2433 {
2434 	/*
2435 	 * SCHED_DEADLINE tasks cannot fork and this is achieved through
2436 	 * sched_fork()
2437 	 */
2438 }
2439 
2440 /* Only try algorithms three times */
2441 #define DL_MAX_TRIES 3
2442 
2443 /*
2444  * Return the earliest pushable rq's task, which is suitable to be executed
2445  * on the CPU, NULL otherwise:
2446  */
pick_earliest_pushable_dl_task(struct rq * rq,int cpu)2447 static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
2448 {
2449 	struct task_struct *p = NULL;
2450 	struct rb_node *next_node;
2451 
2452 	if (!has_pushable_dl_tasks(rq))
2453 		return NULL;
2454 
2455 	next_node = rb_first_cached(&rq->dl.pushable_dl_tasks_root);
2456 	while (next_node) {
2457 		p = __node_2_pdl(next_node);
2458 
2459 		if (task_is_pushable(rq, p, cpu))
2460 			return p;
2461 
2462 		next_node = rb_next(next_node);
2463 	}
2464 
2465 	return NULL;
2466 }
2467 
2468 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
2469 
find_later_rq(struct task_struct * task)2470 static int find_later_rq(struct task_struct *task)
2471 {
2472 	struct sched_domain *sd;
2473 	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
2474 	int this_cpu = smp_processor_id();
2475 	int cpu = task_cpu(task);
2476 
2477 	/* Make sure the mask is initialized first */
2478 	if (unlikely(!later_mask))
2479 		return -1;
2480 
2481 	if (task->nr_cpus_allowed == 1)
2482 		return -1;
2483 
2484 	/*
2485 	 * We have to consider system topology and task affinity
2486 	 * first, then we can look for a suitable CPU.
2487 	 */
2488 	if (!cpudl_find(&task_rq(task)->rd->cpudl, task, later_mask))
2489 		return -1;
2490 
2491 	/*
2492 	 * If we are here, some targets have been found, including
2493 	 * the most suitable which is, among the runqueues where the
2494 	 * current tasks have later deadlines than the task's one, the
2495 	 * rq with the latest possible one.
2496 	 *
2497 	 * Now we check how well this matches with task's
2498 	 * affinity and system topology.
2499 	 *
2500 	 * The last CPU where the task run is our first
2501 	 * guess, since it is most likely cache-hot there.
2502 	 */
2503 	if (cpumask_test_cpu(cpu, later_mask))
2504 		return cpu;
2505 	/*
2506 	 * Check if this_cpu is to be skipped (i.e., it is
2507 	 * not in the mask) or not.
2508 	 */
2509 	if (!cpumask_test_cpu(this_cpu, later_mask))
2510 		this_cpu = -1;
2511 
2512 	rcu_read_lock();
2513 	for_each_domain(cpu, sd) {
2514 		if (sd->flags & SD_WAKE_AFFINE) {
2515 			int best_cpu;
2516 
2517 			/*
2518 			 * If possible, preempting this_cpu is
2519 			 * cheaper than migrating.
2520 			 */
2521 			if (this_cpu != -1 &&
2522 			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
2523 				rcu_read_unlock();
2524 				return this_cpu;
2525 			}
2526 
2527 			best_cpu = cpumask_any_and_distribute(later_mask,
2528 							      sched_domain_span(sd));
2529 			/*
2530 			 * Last chance: if a CPU being in both later_mask
2531 			 * and current sd span is valid, that becomes our
2532 			 * choice. Of course, the latest possible CPU is
2533 			 * already under consideration through later_mask.
2534 			 */
2535 			if (best_cpu < nr_cpu_ids) {
2536 				rcu_read_unlock();
2537 				return best_cpu;
2538 			}
2539 		}
2540 	}
2541 	rcu_read_unlock();
2542 
2543 	/*
2544 	 * At this point, all our guesses failed, we just return
2545 	 * 'something', and let the caller sort the things out.
2546 	 */
2547 	if (this_cpu != -1)
2548 		return this_cpu;
2549 
2550 	cpu = cpumask_any_distribute(later_mask);
2551 	if (cpu < nr_cpu_ids)
2552 		return cpu;
2553 
2554 	return -1;
2555 }
2556 
pick_next_pushable_dl_task(struct rq * rq)2557 static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
2558 {
2559 	struct task_struct *p;
2560 
2561 	if (!has_pushable_dl_tasks(rq))
2562 		return NULL;
2563 
2564 	p = __node_2_pdl(rb_first_cached(&rq->dl.pushable_dl_tasks_root));
2565 
2566 	WARN_ON_ONCE(rq->cpu != task_cpu(p));
2567 	WARN_ON_ONCE(task_current(rq, p));
2568 	WARN_ON_ONCE(p->nr_cpus_allowed <= 1);
2569 
2570 	WARN_ON_ONCE(!task_on_rq_queued(p));
2571 	WARN_ON_ONCE(!dl_task(p));
2572 
2573 	return p;
2574 }
2575 
2576 /* Locks the rq it finds */
find_lock_later_rq(struct task_struct * task,struct rq * rq)2577 static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
2578 {
2579 	struct rq *later_rq = NULL;
2580 	int tries;
2581 	int cpu;
2582 
2583 	for (tries = 0; tries < DL_MAX_TRIES; tries++) {
2584 		cpu = find_later_rq(task);
2585 
2586 		if ((cpu == -1) || (cpu == rq->cpu))
2587 			break;
2588 
2589 		later_rq = cpu_rq(cpu);
2590 
2591 		if (!dl_task_is_earliest_deadline(task, later_rq)) {
2592 			/*
2593 			 * Target rq has tasks of equal or earlier deadline,
2594 			 * retrying does not release any lock and is unlikely
2595 			 * to yield a different result.
2596 			 */
2597 			later_rq = NULL;
2598 			break;
2599 		}
2600 
2601 		/* Retry if something changed. */
2602 		if (double_lock_balance(rq, later_rq)) {
2603 			/*
2604 			 * double_lock_balance had to release rq->lock, in the
2605 			 * meantime, task may no longer be fit to be migrated.
2606 			 * Check the following to ensure that the task is
2607 			 * still suitable for migration:
2608 			 * 1. It is possible the task was scheduled,
2609 			 *    migrate_disabled was set and then got preempted,
2610 			 *    so we must check the task migration disable
2611 			 *    flag.
2612 			 * 2. The CPU picked is in the task's affinity.
2613 			 * 3. For throttled task (dl_task_offline_migration),
2614 			 *    check the following:
2615 			 *    - the task is not on the rq anymore (it was
2616 			 *      migrated)
2617 			 *    - the task is not on CPU anymore
2618 			 *    - the task is still a dl task
2619 			 *    - the task is not queued on the rq anymore
2620 			 * 4. For the non-throttled task (push_dl_task), the
2621 			 *    check to ensure that this task is still at the
2622 			 *    head of the pushable tasks list is enough.
2623 			 */
2624 			if (unlikely(is_migration_disabled(task) ||
2625 				     !cpumask_test_cpu(later_rq->cpu, &task->cpus_mask) ||
2626 				     (task->dl.dl_throttled &&
2627 				      (task_rq(task) != rq ||
2628 				       task_on_cpu(rq, task) ||
2629 				       !dl_task(task) ||
2630 				       !task_on_rq_queued(task))) ||
2631 				     (!task->dl.dl_throttled &&
2632 				      task != pick_next_pushable_dl_task(rq)))) {
2633 
2634 				double_unlock_balance(rq, later_rq);
2635 				later_rq = NULL;
2636 				break;
2637 			}
2638 		}
2639 
2640 		/*
2641 		 * If the rq we found has no -deadline task, or
2642 		 * its earliest one has a later deadline than our
2643 		 * task, the rq is a good one.
2644 		 */
2645 		if (dl_task_is_earliest_deadline(task, later_rq))
2646 			break;
2647 
2648 		/* Otherwise we try again. */
2649 		double_unlock_balance(rq, later_rq);
2650 		later_rq = NULL;
2651 	}
2652 
2653 	return later_rq;
2654 }
2655 
2656 /*
2657  * See if the non running -deadline tasks on this rq
2658  * can be sent to some other CPU where they can preempt
2659  * and start executing.
2660  */
push_dl_task(struct rq * rq)2661 static int push_dl_task(struct rq *rq)
2662 {
2663 	struct task_struct *next_task;
2664 	struct rq *later_rq;
2665 	int ret = 0;
2666 
2667 	next_task = pick_next_pushable_dl_task(rq);
2668 	if (!next_task)
2669 		return 0;
2670 
2671 retry:
2672 	/*
2673 	 * If next_task preempts rq->curr, and rq->curr
2674 	 * can move away, it makes sense to just reschedule
2675 	 * without going further in pushing next_task.
2676 	 */
2677 	if (dl_task(rq->donor) &&
2678 	    dl_time_before(next_task->dl.deadline, rq->donor->dl.deadline) &&
2679 	    rq->curr->nr_cpus_allowed > 1) {
2680 		resched_curr(rq);
2681 		return 0;
2682 	}
2683 
2684 	if (is_migration_disabled(next_task))
2685 		return 0;
2686 
2687 	if (WARN_ON(next_task == rq->curr))
2688 		return 0;
2689 
2690 	/* We might release rq lock */
2691 	get_task_struct(next_task);
2692 
2693 	/* Will lock the rq it'll find */
2694 	later_rq = find_lock_later_rq(next_task, rq);
2695 	if (!later_rq) {
2696 		struct task_struct *task;
2697 
2698 		/*
2699 		 * We must check all this again, since
2700 		 * find_lock_later_rq releases rq->lock and it is
2701 		 * then possible that next_task has migrated.
2702 		 */
2703 		task = pick_next_pushable_dl_task(rq);
2704 		if (task == next_task) {
2705 			/*
2706 			 * The task is still there. We don't try
2707 			 * again, some other CPU will pull it when ready.
2708 			 */
2709 			goto out;
2710 		}
2711 
2712 		if (!task)
2713 			/* No more tasks */
2714 			goto out;
2715 
2716 		put_task_struct(next_task);
2717 		next_task = task;
2718 		goto retry;
2719 	}
2720 
2721 	move_queued_task_locked(rq, later_rq, next_task);
2722 	ret = 1;
2723 
2724 	resched_curr(later_rq);
2725 
2726 	double_unlock_balance(rq, later_rq);
2727 
2728 out:
2729 	put_task_struct(next_task);
2730 
2731 	return ret;
2732 }
2733 
push_dl_tasks(struct rq * rq)2734 static void push_dl_tasks(struct rq *rq)
2735 {
2736 	/* push_dl_task() will return true if it moved a -deadline task */
2737 	while (push_dl_task(rq))
2738 		;
2739 }
2740 
pull_dl_task(struct rq * this_rq)2741 static void pull_dl_task(struct rq *this_rq)
2742 {
2743 	int this_cpu = this_rq->cpu, cpu;
2744 	struct task_struct *p, *push_task;
2745 	bool resched = false;
2746 	struct rq *src_rq;
2747 	u64 dmin = LONG_MAX;
2748 
2749 	if (likely(!dl_overloaded(this_rq)))
2750 		return;
2751 
2752 	/*
2753 	 * Match the barrier from dl_set_overloaded; this guarantees that if we
2754 	 * see overloaded we must also see the dlo_mask bit.
2755 	 */
2756 	smp_rmb();
2757 
2758 	for_each_cpu(cpu, this_rq->rd->dlo_mask) {
2759 		if (this_cpu == cpu)
2760 			continue;
2761 
2762 		src_rq = cpu_rq(cpu);
2763 
2764 		/*
2765 		 * It looks racy, and it is! However, as in sched_rt.c,
2766 		 * we are fine with this.
2767 		 */
2768 		if (this_rq->dl.dl_nr_running &&
2769 		    dl_time_before(this_rq->dl.earliest_dl.curr,
2770 				   src_rq->dl.earliest_dl.next))
2771 			continue;
2772 
2773 		/* Might drop this_rq->lock */
2774 		push_task = NULL;
2775 		double_lock_balance(this_rq, src_rq);
2776 
2777 		/*
2778 		 * If there are no more pullable tasks on the
2779 		 * rq, we're done with it.
2780 		 */
2781 		if (src_rq->dl.dl_nr_running <= 1)
2782 			goto skip;
2783 
2784 		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
2785 
2786 		/*
2787 		 * We found a task to be pulled if:
2788 		 *  - it preempts our current (if there's one),
2789 		 *  - it will preempt the last one we pulled (if any).
2790 		 */
2791 		if (p && dl_time_before(p->dl.deadline, dmin) &&
2792 		    dl_task_is_earliest_deadline(p, this_rq)) {
2793 			WARN_ON(p == src_rq->curr);
2794 			WARN_ON(!task_on_rq_queued(p));
2795 
2796 			/*
2797 			 * Then we pull iff p has actually an earlier
2798 			 * deadline than the current task of its runqueue.
2799 			 */
2800 			if (dl_time_before(p->dl.deadline,
2801 					   src_rq->donor->dl.deadline))
2802 				goto skip;
2803 
2804 			if (is_migration_disabled(p)) {
2805 				push_task = get_push_task(src_rq);
2806 			} else {
2807 				move_queued_task_locked(src_rq, this_rq, p);
2808 				dmin = p->dl.deadline;
2809 				resched = true;
2810 			}
2811 
2812 			/* Is there any other task even earlier? */
2813 		}
2814 skip:
2815 		double_unlock_balance(this_rq, src_rq);
2816 
2817 		if (push_task) {
2818 			preempt_disable();
2819 			raw_spin_rq_unlock(this_rq);
2820 			stop_one_cpu_nowait(src_rq->cpu, push_cpu_stop,
2821 					    push_task, &src_rq->push_work);
2822 			preempt_enable();
2823 			raw_spin_rq_lock(this_rq);
2824 		}
2825 	}
2826 
2827 	if (resched)
2828 		resched_curr(this_rq);
2829 }
2830 
2831 /*
2832  * Since the task is not running and a reschedule is not going to happen
2833  * anytime soon on its runqueue, we try pushing it away now.
2834  */
task_woken_dl(struct rq * rq,struct task_struct * p)2835 static void task_woken_dl(struct rq *rq, struct task_struct *p)
2836 {
2837 	if (!task_on_cpu(rq, p) &&
2838 	    !test_tsk_need_resched(rq->curr) &&
2839 	    p->nr_cpus_allowed > 1 &&
2840 	    dl_task(rq->donor) &&
2841 	    (rq->curr->nr_cpus_allowed < 2 ||
2842 	     !dl_entity_preempt(&p->dl, &rq->donor->dl))) {
2843 		push_dl_tasks(rq);
2844 	}
2845 }
2846 
set_cpus_allowed_dl(struct task_struct * p,struct affinity_context * ctx)2847 static void set_cpus_allowed_dl(struct task_struct *p,
2848 				struct affinity_context *ctx)
2849 {
2850 	struct root_domain *src_rd;
2851 	struct rq *rq;
2852 
2853 	WARN_ON_ONCE(!dl_task(p));
2854 
2855 	rq = task_rq(p);
2856 	src_rd = rq->rd;
2857 	/*
2858 	 * Migrating a SCHED_DEADLINE task between exclusive
2859 	 * cpusets (different root_domains) entails a bandwidth
2860 	 * update. We already made space for us in the destination
2861 	 * domain (see cpuset_can_attach()).
2862 	 */
2863 	if (!cpumask_intersects(src_rd->span, ctx->new_mask)) {
2864 		struct dl_bw *src_dl_b;
2865 
2866 		src_dl_b = dl_bw_of(cpu_of(rq));
2867 		/*
2868 		 * We now free resources of the root_domain we are migrating
2869 		 * off. In the worst case, sched_setattr() may temporary fail
2870 		 * until we complete the update.
2871 		 */
2872 		raw_spin_lock(&src_dl_b->lock);
2873 		__dl_sub(src_dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
2874 		raw_spin_unlock(&src_dl_b->lock);
2875 	}
2876 
2877 	set_cpus_allowed_common(p, ctx);
2878 }
2879 
2880 /* Assumes rq->lock is held */
rq_online_dl(struct rq * rq)2881 static void rq_online_dl(struct rq *rq)
2882 {
2883 	if (rq->dl.overloaded)
2884 		dl_set_overload(rq);
2885 
2886 	cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
2887 	if (rq->dl.dl_nr_running > 0)
2888 		cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr);
2889 }
2890 
2891 /* Assumes rq->lock is held */
rq_offline_dl(struct rq * rq)2892 static void rq_offline_dl(struct rq *rq)
2893 {
2894 	if (rq->dl.overloaded)
2895 		dl_clear_overload(rq);
2896 
2897 	cpudl_clear(&rq->rd->cpudl, rq->cpu);
2898 	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
2899 }
2900 
init_sched_dl_class(void)2901 void __init init_sched_dl_class(void)
2902 {
2903 	unsigned int i;
2904 
2905 	for_each_possible_cpu(i)
2906 		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
2907 					GFP_KERNEL, cpu_to_node(i));
2908 }
2909 
dl_add_task_root_domain(struct task_struct * p)2910 void dl_add_task_root_domain(struct task_struct *p)
2911 {
2912 	struct rq_flags rf;
2913 	struct rq *rq;
2914 	struct dl_bw *dl_b;
2915 
2916 	raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
2917 	if (!dl_task(p) || dl_entity_is_special(&p->dl)) {
2918 		raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
2919 		return;
2920 	}
2921 
2922 	rq = __task_rq_lock(p, &rf);
2923 
2924 	dl_b = &rq->rd->dl_bw;
2925 	raw_spin_lock(&dl_b->lock);
2926 
2927 	__dl_add(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span));
2928 
2929 	raw_spin_unlock(&dl_b->lock);
2930 
2931 	task_rq_unlock(rq, p, &rf);
2932 }
2933 
dl_clear_root_domain(struct root_domain * rd)2934 void dl_clear_root_domain(struct root_domain *rd)
2935 {
2936 	int i;
2937 
2938 	guard(raw_spinlock_irqsave)(&rd->dl_bw.lock);
2939 
2940 	/*
2941 	 * Reset total_bw to zero and extra_bw to max_bw so that next
2942 	 * loop will add dl-servers contributions back properly,
2943 	 */
2944 	rd->dl_bw.total_bw = 0;
2945 	for_each_cpu(i, rd->span)
2946 		cpu_rq(i)->dl.extra_bw = cpu_rq(i)->dl.max_bw;
2947 
2948 	/*
2949 	 * dl_servers are not tasks. Since dl_add_task_root_domain ignores
2950 	 * them, we need to account for them here explicitly.
2951 	 */
2952 	for_each_cpu(i, rd->span) {
2953 		struct sched_dl_entity *dl_se = &cpu_rq(i)->fair_server;
2954 
2955 		if (dl_server(dl_se) && cpu_active(i))
2956 			__dl_add(&rd->dl_bw, dl_se->dl_bw, dl_bw_cpus(i));
2957 	}
2958 }
2959 
dl_clear_root_domain_cpu(int cpu)2960 void dl_clear_root_domain_cpu(int cpu)
2961 {
2962 	dl_clear_root_domain(cpu_rq(cpu)->rd);
2963 }
2964 
switched_from_dl(struct rq * rq,struct task_struct * p)2965 static void switched_from_dl(struct rq *rq, struct task_struct *p)
2966 {
2967 	/*
2968 	 * task_non_contending() can start the "inactive timer" (if the 0-lag
2969 	 * time is in the future). If the task switches back to dl before
2970 	 * the "inactive timer" fires, it can continue to consume its current
2971 	 * runtime using its current deadline. If it stays outside of
2972 	 * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer()
2973 	 * will reset the task parameters.
2974 	 */
2975 	if (task_on_rq_queued(p) && p->dl.dl_runtime)
2976 		task_non_contending(&p->dl);
2977 
2978 	/*
2979 	 * In case a task is setscheduled out from SCHED_DEADLINE we need to
2980 	 * keep track of that on its cpuset (for correct bandwidth tracking).
2981 	 */
2982 	dec_dl_tasks_cs(p);
2983 
2984 	if (!task_on_rq_queued(p)) {
2985 		/*
2986 		 * Inactive timer is armed. However, p is leaving DEADLINE and
2987 		 * might migrate away from this rq while continuing to run on
2988 		 * some other class. We need to remove its contribution from
2989 		 * this rq running_bw now, or sub_rq_bw (below) will complain.
2990 		 */
2991 		if (p->dl.dl_non_contending)
2992 			sub_running_bw(&p->dl, &rq->dl);
2993 		sub_rq_bw(&p->dl, &rq->dl);
2994 	}
2995 
2996 	/*
2997 	 * We cannot use inactive_task_timer() to invoke sub_running_bw()
2998 	 * at the 0-lag time, because the task could have been migrated
2999 	 * while SCHED_OTHER in the meanwhile.
3000 	 */
3001 	if (p->dl.dl_non_contending)
3002 		p->dl.dl_non_contending = 0;
3003 
3004 	/*
3005 	 * Since this might be the only -deadline task on the rq,
3006 	 * this is the right place to try to pull some other one
3007 	 * from an overloaded CPU, if any.
3008 	 */
3009 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
3010 		return;
3011 
3012 	deadline_queue_pull_task(rq);
3013 }
3014 
3015 /*
3016  * When switching to -deadline, we may overload the rq, then
3017  * we try to push someone off, if possible.
3018  */
switched_to_dl(struct rq * rq,struct task_struct * p)3019 static void switched_to_dl(struct rq *rq, struct task_struct *p)
3020 {
3021 	cancel_inactive_timer(&p->dl);
3022 
3023 	/*
3024 	 * In case a task is setscheduled to SCHED_DEADLINE we need to keep
3025 	 * track of that on its cpuset (for correct bandwidth tracking).
3026 	 */
3027 	inc_dl_tasks_cs(p);
3028 
3029 	/* If p is not queued we will update its parameters at next wakeup. */
3030 	if (!task_on_rq_queued(p)) {
3031 		add_rq_bw(&p->dl, &rq->dl);
3032 
3033 		return;
3034 	}
3035 
3036 	if (rq->donor != p) {
3037 		if (p->nr_cpus_allowed > 1 && rq->dl.overloaded)
3038 			deadline_queue_push_tasks(rq);
3039 		if (dl_task(rq->donor))
3040 			wakeup_preempt_dl(rq, p, 0);
3041 		else
3042 			resched_curr(rq);
3043 	} else {
3044 		update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
3045 	}
3046 }
3047 
3048 /*
3049  * If the scheduling parameters of a -deadline task changed,
3050  * a push or pull operation might be needed.
3051  */
prio_changed_dl(struct rq * rq,struct task_struct * p,int oldprio)3052 static void prio_changed_dl(struct rq *rq, struct task_struct *p,
3053 			    int oldprio)
3054 {
3055 	if (!task_on_rq_queued(p))
3056 		return;
3057 
3058 	/*
3059 	 * This might be too much, but unfortunately
3060 	 * we don't have the old deadline value, and
3061 	 * we can't argue if the task is increasing
3062 	 * or lowering its prio, so...
3063 	 */
3064 	if (!rq->dl.overloaded)
3065 		deadline_queue_pull_task(rq);
3066 
3067 	if (task_current_donor(rq, p)) {
3068 		/*
3069 		 * If we now have a earlier deadline task than p,
3070 		 * then reschedule, provided p is still on this
3071 		 * runqueue.
3072 		 */
3073 		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))
3074 			resched_curr(rq);
3075 	} else {
3076 		/*
3077 		 * Current may not be deadline in case p was throttled but we
3078 		 * have just replenished it (e.g. rt_mutex_setprio()).
3079 		 *
3080 		 * Otherwise, if p was given an earlier deadline, reschedule.
3081 		 */
3082 		if (!dl_task(rq->curr) ||
3083 		    dl_time_before(p->dl.deadline, rq->curr->dl.deadline))
3084 			resched_curr(rq);
3085 	}
3086 }
3087 
3088 #ifdef CONFIG_SCHED_CORE
task_is_throttled_dl(struct task_struct * p,int cpu)3089 static int task_is_throttled_dl(struct task_struct *p, int cpu)
3090 {
3091 	return p->dl.dl_throttled;
3092 }
3093 #endif
3094 
3095 DEFINE_SCHED_CLASS(dl) = {
3096 
3097 	.enqueue_task		= enqueue_task_dl,
3098 	.dequeue_task		= dequeue_task_dl,
3099 	.yield_task		= yield_task_dl,
3100 
3101 	.wakeup_preempt		= wakeup_preempt_dl,
3102 
3103 	.pick_task		= pick_task_dl,
3104 	.put_prev_task		= put_prev_task_dl,
3105 	.set_next_task		= set_next_task_dl,
3106 
3107 	.balance		= balance_dl,
3108 	.select_task_rq		= select_task_rq_dl,
3109 	.migrate_task_rq	= migrate_task_rq_dl,
3110 	.set_cpus_allowed       = set_cpus_allowed_dl,
3111 	.rq_online              = rq_online_dl,
3112 	.rq_offline             = rq_offline_dl,
3113 	.task_woken		= task_woken_dl,
3114 	.find_lock_rq		= find_lock_later_rq,
3115 
3116 	.task_tick		= task_tick_dl,
3117 	.task_fork              = task_fork_dl,
3118 
3119 	.prio_changed           = prio_changed_dl,
3120 	.switched_from		= switched_from_dl,
3121 	.switched_to		= switched_to_dl,
3122 
3123 	.update_curr		= update_curr_dl,
3124 #ifdef CONFIG_SCHED_CORE
3125 	.task_is_throttled	= task_is_throttled_dl,
3126 #endif
3127 };
3128 
3129 /*
3130  * Used for dl_bw check and update, used under sched_rt_handler()::mutex and
3131  * sched_domains_mutex.
3132  */
3133 u64 dl_cookie;
3134 
sched_dl_global_validate(void)3135 int sched_dl_global_validate(void)
3136 {
3137 	u64 runtime = global_rt_runtime();
3138 	u64 period = global_rt_period();
3139 	u64 new_bw = to_ratio(period, runtime);
3140 	u64 cookie = ++dl_cookie;
3141 	struct dl_bw *dl_b;
3142 	int cpu, cpus, ret = 0;
3143 	unsigned long flags;
3144 
3145 	/*
3146 	 * Here we want to check the bandwidth not being set to some
3147 	 * value smaller than the currently allocated bandwidth in
3148 	 * any of the root_domains.
3149 	 */
3150 	for_each_online_cpu(cpu) {
3151 		rcu_read_lock_sched();
3152 
3153 		if (dl_bw_visited(cpu, cookie))
3154 			goto next;
3155 
3156 		dl_b = dl_bw_of(cpu);
3157 		cpus = dl_bw_cpus(cpu);
3158 
3159 		raw_spin_lock_irqsave(&dl_b->lock, flags);
3160 		if (new_bw * cpus < dl_b->total_bw)
3161 			ret = -EBUSY;
3162 		raw_spin_unlock_irqrestore(&dl_b->lock, flags);
3163 
3164 next:
3165 		rcu_read_unlock_sched();
3166 
3167 		if (ret)
3168 			break;
3169 	}
3170 
3171 	return ret;
3172 }
3173 
init_dl_rq_bw_ratio(struct dl_rq * dl_rq)3174 static void init_dl_rq_bw_ratio(struct dl_rq *dl_rq)
3175 {
3176 	if (global_rt_runtime() == RUNTIME_INF) {
3177 		dl_rq->bw_ratio = 1 << RATIO_SHIFT;
3178 		dl_rq->max_bw = dl_rq->extra_bw = 1 << BW_SHIFT;
3179 	} else {
3180 		dl_rq->bw_ratio = to_ratio(global_rt_runtime(),
3181 			  global_rt_period()) >> (BW_SHIFT - RATIO_SHIFT);
3182 		dl_rq->max_bw = dl_rq->extra_bw =
3183 			to_ratio(global_rt_period(), global_rt_runtime());
3184 	}
3185 }
3186 
sched_dl_do_global(void)3187 void sched_dl_do_global(void)
3188 {
3189 	u64 new_bw = -1;
3190 	u64 cookie = ++dl_cookie;
3191 	struct dl_bw *dl_b;
3192 	int cpu;
3193 	unsigned long flags;
3194 
3195 	if (global_rt_runtime() != RUNTIME_INF)
3196 		new_bw = to_ratio(global_rt_period(), global_rt_runtime());
3197 
3198 	for_each_possible_cpu(cpu)
3199 		init_dl_rq_bw_ratio(&cpu_rq(cpu)->dl);
3200 
3201 	for_each_possible_cpu(cpu) {
3202 		rcu_read_lock_sched();
3203 
3204 		if (dl_bw_visited(cpu, cookie)) {
3205 			rcu_read_unlock_sched();
3206 			continue;
3207 		}
3208 
3209 		dl_b = dl_bw_of(cpu);
3210 
3211 		raw_spin_lock_irqsave(&dl_b->lock, flags);
3212 		dl_b->bw = new_bw;
3213 		raw_spin_unlock_irqrestore(&dl_b->lock, flags);
3214 
3215 		rcu_read_unlock_sched();
3216 	}
3217 }
3218 
3219 /*
3220  * We must be sure that accepting a new task (or allowing changing the
3221  * parameters of an existing one) is consistent with the bandwidth
3222  * constraints. If yes, this function also accordingly updates the currently
3223  * allocated bandwidth to reflect the new situation.
3224  *
3225  * This function is called while holding p's rq->lock.
3226  */
sched_dl_overflow(struct task_struct * p,int policy,const struct sched_attr * attr)3227 int sched_dl_overflow(struct task_struct *p, int policy,
3228 		      const struct sched_attr *attr)
3229 {
3230 	u64 period = attr->sched_period ?: attr->sched_deadline;
3231 	u64 runtime = attr->sched_runtime;
3232 	u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
3233 	int cpus, err = -1, cpu = task_cpu(p);
3234 	struct dl_bw *dl_b = dl_bw_of(cpu);
3235 	unsigned long cap;
3236 
3237 	if (attr->sched_flags & SCHED_FLAG_SUGOV)
3238 		return 0;
3239 
3240 	/* !deadline task may carry old deadline bandwidth */
3241 	if (new_bw == p->dl.dl_bw && task_has_dl_policy(p))
3242 		return 0;
3243 
3244 	/*
3245 	 * Either if a task, enters, leave, or stays -deadline but changes
3246 	 * its parameters, we may need to update accordingly the total
3247 	 * allocated bandwidth of the container.
3248 	 */
3249 	raw_spin_lock(&dl_b->lock);
3250 	cpus = dl_bw_cpus(cpu);
3251 	cap = dl_bw_capacity(cpu);
3252 
3253 	if (dl_policy(policy) && !task_has_dl_policy(p) &&
3254 	    !__dl_overflow(dl_b, cap, 0, new_bw)) {
3255 		if (hrtimer_active(&p->dl.inactive_timer))
3256 			__dl_sub(dl_b, p->dl.dl_bw, cpus);
3257 		__dl_add(dl_b, new_bw, cpus);
3258 		err = 0;
3259 	} else if (dl_policy(policy) && task_has_dl_policy(p) &&
3260 		   !__dl_overflow(dl_b, cap, p->dl.dl_bw, new_bw)) {
3261 		/*
3262 		 * XXX this is slightly incorrect: when the task
3263 		 * utilization decreases, we should delay the total
3264 		 * utilization change until the task's 0-lag point.
3265 		 * But this would require to set the task's "inactive
3266 		 * timer" when the task is not inactive.
3267 		 */
3268 		__dl_sub(dl_b, p->dl.dl_bw, cpus);
3269 		__dl_add(dl_b, new_bw, cpus);
3270 		dl_change_utilization(p, new_bw);
3271 		err = 0;
3272 	} else if (!dl_policy(policy) && task_has_dl_policy(p)) {
3273 		/*
3274 		 * Do not decrease the total deadline utilization here,
3275 		 * switched_from_dl() will take care to do it at the correct
3276 		 * (0-lag) time.
3277 		 */
3278 		err = 0;
3279 	}
3280 	raw_spin_unlock(&dl_b->lock);
3281 
3282 	return err;
3283 }
3284 
3285 /*
3286  * This function initializes the sched_dl_entity of a newly becoming
3287  * SCHED_DEADLINE task.
3288  *
3289  * Only the static values are considered here, the actual runtime and the
3290  * absolute deadline will be properly calculated when the task is enqueued
3291  * for the first time with its new policy.
3292  */
__setparam_dl(struct task_struct * p,const struct sched_attr * attr)3293 void __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
3294 {
3295 	struct sched_dl_entity *dl_se = &p->dl;
3296 
3297 	dl_se->dl_runtime = attr->sched_runtime;
3298 	dl_se->dl_deadline = attr->sched_deadline;
3299 	dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
3300 	dl_se->flags = attr->sched_flags & SCHED_DL_FLAGS;
3301 	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
3302 	dl_se->dl_density = to_ratio(dl_se->dl_deadline, dl_se->dl_runtime);
3303 }
3304 
__getparam_dl(struct task_struct * p,struct sched_attr * attr)3305 void __getparam_dl(struct task_struct *p, struct sched_attr *attr)
3306 {
3307 	struct sched_dl_entity *dl_se = &p->dl;
3308 
3309 	attr->sched_priority = p->rt_priority;
3310 	attr->sched_runtime = dl_se->dl_runtime;
3311 	attr->sched_deadline = dl_se->dl_deadline;
3312 	attr->sched_period = dl_se->dl_period;
3313 	attr->sched_flags &= ~SCHED_DL_FLAGS;
3314 	attr->sched_flags |= dl_se->flags;
3315 }
3316 
3317 /*
3318  * This function validates the new parameters of a -deadline task.
3319  * We ask for the deadline not being zero, and greater or equal
3320  * than the runtime, as well as the period of being zero or
3321  * greater than deadline. Furthermore, we have to be sure that
3322  * user parameters are above the internal resolution of 1us (we
3323  * check sched_runtime only since it is always the smaller one) and
3324  * below 2^63 ns (we have to check both sched_deadline and
3325  * sched_period, as the latter can be zero).
3326  */
__checkparam_dl(const struct sched_attr * attr)3327 bool __checkparam_dl(const struct sched_attr *attr)
3328 {
3329 	u64 period, max, min;
3330 
3331 	/* special dl tasks don't actually use any parameter */
3332 	if (attr->sched_flags & SCHED_FLAG_SUGOV)
3333 		return true;
3334 
3335 	/* deadline != 0 */
3336 	if (attr->sched_deadline == 0)
3337 		return false;
3338 
3339 	/*
3340 	 * Since we truncate DL_SCALE bits, make sure we're at least
3341 	 * that big.
3342 	 */
3343 	if (attr->sched_runtime < (1ULL << DL_SCALE))
3344 		return false;
3345 
3346 	/*
3347 	 * Since we use the MSB for wrap-around and sign issues, make
3348 	 * sure it's not set (mind that period can be equal to zero).
3349 	 */
3350 	if (attr->sched_deadline & (1ULL << 63) ||
3351 	    attr->sched_period & (1ULL << 63))
3352 		return false;
3353 
3354 	period = attr->sched_period;
3355 	if (!period)
3356 		period = attr->sched_deadline;
3357 
3358 	/* runtime <= deadline <= period (if period != 0) */
3359 	if (period < attr->sched_deadline ||
3360 	    attr->sched_deadline < attr->sched_runtime)
3361 		return false;
3362 
3363 	max = (u64)READ_ONCE(sysctl_sched_dl_period_max) * NSEC_PER_USEC;
3364 	min = (u64)READ_ONCE(sysctl_sched_dl_period_min) * NSEC_PER_USEC;
3365 
3366 	if (period < min || period > max)
3367 		return false;
3368 
3369 	return true;
3370 }
3371 
3372 /*
3373  * This function clears the sched_dl_entity static params.
3374  */
__dl_clear_params(struct sched_dl_entity * dl_se)3375 static void __dl_clear_params(struct sched_dl_entity *dl_se)
3376 {
3377 	dl_se->dl_runtime		= 0;
3378 	dl_se->dl_deadline		= 0;
3379 	dl_se->dl_period		= 0;
3380 	dl_se->flags			= 0;
3381 	dl_se->dl_bw			= 0;
3382 	dl_se->dl_density		= 0;
3383 
3384 	dl_se->dl_throttled		= 0;
3385 	dl_se->dl_yielded		= 0;
3386 	dl_se->dl_non_contending	= 0;
3387 	dl_se->dl_overrun		= 0;
3388 	dl_se->dl_server		= 0;
3389 
3390 #ifdef CONFIG_RT_MUTEXES
3391 	dl_se->pi_se			= dl_se;
3392 #endif
3393 }
3394 
init_dl_entity(struct sched_dl_entity * dl_se)3395 void init_dl_entity(struct sched_dl_entity *dl_se)
3396 {
3397 	RB_CLEAR_NODE(&dl_se->rb_node);
3398 	init_dl_task_timer(dl_se);
3399 	init_dl_inactive_task_timer(dl_se);
3400 	__dl_clear_params(dl_se);
3401 }
3402 
dl_param_changed(struct task_struct * p,const struct sched_attr * attr)3403 bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)
3404 {
3405 	struct sched_dl_entity *dl_se = &p->dl;
3406 
3407 	if (dl_se->dl_runtime != attr->sched_runtime ||
3408 	    dl_se->dl_deadline != attr->sched_deadline ||
3409 	    dl_se->dl_period != attr->sched_period ||
3410 	    dl_se->flags != (attr->sched_flags & SCHED_DL_FLAGS))
3411 		return true;
3412 
3413 	return false;
3414 }
3415 
dl_cpuset_cpumask_can_shrink(const struct cpumask * cur,const struct cpumask * trial)3416 int dl_cpuset_cpumask_can_shrink(const struct cpumask *cur,
3417 				 const struct cpumask *trial)
3418 {
3419 	unsigned long flags, cap;
3420 	struct dl_bw *cur_dl_b;
3421 	int ret = 1;
3422 
3423 	rcu_read_lock_sched();
3424 	cur_dl_b = dl_bw_of(cpumask_any(cur));
3425 	cap = __dl_bw_capacity(trial);
3426 	raw_spin_lock_irqsave(&cur_dl_b->lock, flags);
3427 	if (__dl_overflow(cur_dl_b, cap, 0, 0))
3428 		ret = 0;
3429 	raw_spin_unlock_irqrestore(&cur_dl_b->lock, flags);
3430 	rcu_read_unlock_sched();
3431 
3432 	return ret;
3433 }
3434 
3435 enum dl_bw_request {
3436 	dl_bw_req_deactivate = 0,
3437 	dl_bw_req_alloc,
3438 	dl_bw_req_free
3439 };
3440 
dl_bw_manage(enum dl_bw_request req,int cpu,u64 dl_bw)3441 static int dl_bw_manage(enum dl_bw_request req, int cpu, u64 dl_bw)
3442 {
3443 	unsigned long flags, cap;
3444 	struct dl_bw *dl_b;
3445 	bool overflow = 0;
3446 	u64 fair_server_bw = 0;
3447 
3448 	rcu_read_lock_sched();
3449 	dl_b = dl_bw_of(cpu);
3450 	raw_spin_lock_irqsave(&dl_b->lock, flags);
3451 
3452 	cap = dl_bw_capacity(cpu);
3453 	switch (req) {
3454 	case dl_bw_req_free:
3455 		__dl_sub(dl_b, dl_bw, dl_bw_cpus(cpu));
3456 		break;
3457 	case dl_bw_req_alloc:
3458 		overflow = __dl_overflow(dl_b, cap, 0, dl_bw);
3459 
3460 		if (!overflow) {
3461 			/*
3462 			 * We reserve space in the destination
3463 			 * root_domain, as we can't fail after this point.
3464 			 * We will free resources in the source root_domain
3465 			 * later on (see set_cpus_allowed_dl()).
3466 			 */
3467 			__dl_add(dl_b, dl_bw, dl_bw_cpus(cpu));
3468 		}
3469 		break;
3470 	case dl_bw_req_deactivate:
3471 		/*
3472 		 * cpu is not off yet, but we need to do the math by
3473 		 * considering it off already (i.e., what would happen if we
3474 		 * turn cpu off?).
3475 		 */
3476 		cap -= arch_scale_cpu_capacity(cpu);
3477 
3478 		/*
3479 		 * cpu is going offline and NORMAL tasks will be moved away
3480 		 * from it. We can thus discount dl_server bandwidth
3481 		 * contribution as it won't need to be servicing tasks after
3482 		 * the cpu is off.
3483 		 */
3484 		if (cpu_rq(cpu)->fair_server.dl_server)
3485 			fair_server_bw = cpu_rq(cpu)->fair_server.dl_bw;
3486 
3487 		/*
3488 		 * Not much to check if no DEADLINE bandwidth is present.
3489 		 * dl_servers we can discount, as tasks will be moved out the
3490 		 * offlined CPUs anyway.
3491 		 */
3492 		if (dl_b->total_bw - fair_server_bw > 0) {
3493 			/*
3494 			 * Leaving at least one CPU for DEADLINE tasks seems a
3495 			 * wise thing to do. As said above, cpu is not offline
3496 			 * yet, so account for that.
3497 			 */
3498 			if (dl_bw_cpus(cpu) - 1)
3499 				overflow = __dl_overflow(dl_b, cap, fair_server_bw, 0);
3500 			else
3501 				overflow = 1;
3502 		}
3503 
3504 		break;
3505 	}
3506 
3507 	raw_spin_unlock_irqrestore(&dl_b->lock, flags);
3508 	rcu_read_unlock_sched();
3509 
3510 	return overflow ? -EBUSY : 0;
3511 }
3512 
dl_bw_deactivate(int cpu)3513 int dl_bw_deactivate(int cpu)
3514 {
3515 	return dl_bw_manage(dl_bw_req_deactivate, cpu, 0);
3516 }
3517 
dl_bw_alloc(int cpu,u64 dl_bw)3518 int dl_bw_alloc(int cpu, u64 dl_bw)
3519 {
3520 	return dl_bw_manage(dl_bw_req_alloc, cpu, dl_bw);
3521 }
3522 
dl_bw_free(int cpu,u64 dl_bw)3523 void dl_bw_free(int cpu, u64 dl_bw)
3524 {
3525 	dl_bw_manage(dl_bw_req_free, cpu, dl_bw);
3526 }
3527 
print_dl_stats(struct seq_file * m,int cpu)3528 void print_dl_stats(struct seq_file *m, int cpu)
3529 {
3530 	print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
3531 }
3532