xref: /linux/kernel/sched/deadline.c (revision e0bf6c5ca2d3281f231c5f0c9bf145e9513644de)
1 /*
2  * Deadline Scheduling Class (SCHED_DEADLINE)
3  *
4  * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
5  *
6  * Tasks that periodically executes their instances for less than their
7  * runtime won't miss any of their deadlines.
8  * Tasks that are not periodic or sporadic or that tries to execute more
9  * than their reserved bandwidth will be slowed down (and may potentially
10  * miss some of their deadlines), and won't affect any other task.
11  *
12  * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>,
13  *                    Juri Lelli <juri.lelli@gmail.com>,
14  *                    Michael Trimarchi <michael@amarulasolutions.com>,
15  *                    Fabio Checconi <fchecconi@gmail.com>
16  */
17 #include "sched.h"
18 
19 #include <linux/slab.h>
20 
21 struct dl_bandwidth def_dl_bandwidth;
22 
23 static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
24 {
25 	return container_of(dl_se, struct task_struct, dl);
26 }
27 
28 static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
29 {
30 	return container_of(dl_rq, struct rq, dl);
31 }
32 
33 static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
34 {
35 	struct task_struct *p = dl_task_of(dl_se);
36 	struct rq *rq = task_rq(p);
37 
38 	return &rq->dl;
39 }
40 
41 static inline int on_dl_rq(struct sched_dl_entity *dl_se)
42 {
43 	return !RB_EMPTY_NODE(&dl_se->rb_node);
44 }
45 
46 static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
47 {
48 	struct sched_dl_entity *dl_se = &p->dl;
49 
50 	return dl_rq->rb_leftmost == &dl_se->rb_node;
51 }
52 
53 void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
54 {
55 	raw_spin_lock_init(&dl_b->dl_runtime_lock);
56 	dl_b->dl_period = period;
57 	dl_b->dl_runtime = runtime;
58 }
59 
60 void init_dl_bw(struct dl_bw *dl_b)
61 {
62 	raw_spin_lock_init(&dl_b->lock);
63 	raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock);
64 	if (global_rt_runtime() == RUNTIME_INF)
65 		dl_b->bw = -1;
66 	else
67 		dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
68 	raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
69 	dl_b->total_bw = 0;
70 }
71 
72 void init_dl_rq(struct dl_rq *dl_rq, struct rq *rq)
73 {
74 	dl_rq->rb_root = RB_ROOT;
75 
76 #ifdef CONFIG_SMP
77 	/* zero means no -deadline tasks */
78 	dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;
79 
80 	dl_rq->dl_nr_migratory = 0;
81 	dl_rq->overloaded = 0;
82 	dl_rq->pushable_dl_tasks_root = RB_ROOT;
83 #else
84 	init_dl_bw(&dl_rq->dl_bw);
85 #endif
86 }
87 
88 #ifdef CONFIG_SMP
89 
90 static inline int dl_overloaded(struct rq *rq)
91 {
92 	return atomic_read(&rq->rd->dlo_count);
93 }
94 
95 static inline void dl_set_overload(struct rq *rq)
96 {
97 	if (!rq->online)
98 		return;
99 
100 	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
101 	/*
102 	 * Must be visible before the overload count is
103 	 * set (as in sched_rt.c).
104 	 *
105 	 * Matched by the barrier in pull_dl_task().
106 	 */
107 	smp_wmb();
108 	atomic_inc(&rq->rd->dlo_count);
109 }
110 
111 static inline void dl_clear_overload(struct rq *rq)
112 {
113 	if (!rq->online)
114 		return;
115 
116 	atomic_dec(&rq->rd->dlo_count);
117 	cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
118 }
119 
120 static void update_dl_migration(struct dl_rq *dl_rq)
121 {
122 	if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) {
123 		if (!dl_rq->overloaded) {
124 			dl_set_overload(rq_of_dl_rq(dl_rq));
125 			dl_rq->overloaded = 1;
126 		}
127 	} else if (dl_rq->overloaded) {
128 		dl_clear_overload(rq_of_dl_rq(dl_rq));
129 		dl_rq->overloaded = 0;
130 	}
131 }
132 
133 static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
134 {
135 	struct task_struct *p = dl_task_of(dl_se);
136 
137 	if (p->nr_cpus_allowed > 1)
138 		dl_rq->dl_nr_migratory++;
139 
140 	update_dl_migration(dl_rq);
141 }
142 
143 static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
144 {
145 	struct task_struct *p = dl_task_of(dl_se);
146 
147 	if (p->nr_cpus_allowed > 1)
148 		dl_rq->dl_nr_migratory--;
149 
150 	update_dl_migration(dl_rq);
151 }
152 
153 /*
154  * The list of pushable -deadline task is not a plist, like in
155  * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
156  */
157 static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
158 {
159 	struct dl_rq *dl_rq = &rq->dl;
160 	struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_node;
161 	struct rb_node *parent = NULL;
162 	struct task_struct *entry;
163 	int leftmost = 1;
164 
165 	BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
166 
167 	while (*link) {
168 		parent = *link;
169 		entry = rb_entry(parent, struct task_struct,
170 				 pushable_dl_tasks);
171 		if (dl_entity_preempt(&p->dl, &entry->dl))
172 			link = &parent->rb_left;
173 		else {
174 			link = &parent->rb_right;
175 			leftmost = 0;
176 		}
177 	}
178 
179 	if (leftmost)
180 		dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
181 
182 	rb_link_node(&p->pushable_dl_tasks, parent, link);
183 	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
184 }
185 
186 static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
187 {
188 	struct dl_rq *dl_rq = &rq->dl;
189 
190 	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
191 		return;
192 
193 	if (dl_rq->pushable_dl_tasks_leftmost == &p->pushable_dl_tasks) {
194 		struct rb_node *next_node;
195 
196 		next_node = rb_next(&p->pushable_dl_tasks);
197 		dl_rq->pushable_dl_tasks_leftmost = next_node;
198 	}
199 
200 	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
201 	RB_CLEAR_NODE(&p->pushable_dl_tasks);
202 }
203 
204 static inline int has_pushable_dl_tasks(struct rq *rq)
205 {
206 	return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
207 }
208 
209 static int push_dl_task(struct rq *rq);
210 
211 static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
212 {
213 	return dl_task(prev);
214 }
215 
216 static inline void set_post_schedule(struct rq *rq)
217 {
218 	rq->post_schedule = has_pushable_dl_tasks(rq);
219 }
220 
221 #else
222 
223 static inline
224 void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
225 {
226 }
227 
228 static inline
229 void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
230 {
231 }
232 
233 static inline
234 void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
235 {
236 }
237 
238 static inline
239 void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
240 {
241 }
242 
243 static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
244 {
245 	return false;
246 }
247 
248 static inline int pull_dl_task(struct rq *rq)
249 {
250 	return 0;
251 }
252 
253 static inline void set_post_schedule(struct rq *rq)
254 {
255 }
256 #endif /* CONFIG_SMP */
257 
258 static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
259 static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags);
260 static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
261 				  int flags);
262 
263 /*
264  * We are being explicitly informed that a new instance is starting,
265  * and this means that:
266  *  - the absolute deadline of the entity has to be placed at
267  *    current time + relative deadline;
268  *  - the runtime of the entity has to be set to the maximum value.
269  *
270  * The capability of specifying such event is useful whenever a -deadline
271  * entity wants to (try to!) synchronize its behaviour with the scheduler's
272  * one, and to (try to!) reconcile itself with its own scheduling
273  * parameters.
274  */
275 static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se,
276 				       struct sched_dl_entity *pi_se)
277 {
278 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
279 	struct rq *rq = rq_of_dl_rq(dl_rq);
280 
281 	WARN_ON(!dl_se->dl_new || dl_se->dl_throttled);
282 
283 	/*
284 	 * We use the regular wall clock time to set deadlines in the
285 	 * future; in fact, we must consider execution overheads (time
286 	 * spent on hardirq context, etc.).
287 	 */
288 	dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
289 	dl_se->runtime = pi_se->dl_runtime;
290 	dl_se->dl_new = 0;
291 }
292 
293 /*
294  * Pure Earliest Deadline First (EDF) scheduling does not deal with the
295  * possibility of a entity lasting more than what it declared, and thus
296  * exhausting its runtime.
297  *
298  * Here we are interested in making runtime overrun possible, but we do
299  * not want a entity which is misbehaving to affect the scheduling of all
300  * other entities.
301  * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
302  * is used, in order to confine each entity within its own bandwidth.
303  *
304  * This function deals exactly with that, and ensures that when the runtime
305  * of a entity is replenished, its deadline is also postponed. That ensures
306  * the overrunning entity can't interfere with other entity in the system and
307  * can't make them miss their deadlines. Reasons why this kind of overruns
308  * could happen are, typically, a entity voluntarily trying to overcome its
309  * runtime, or it just underestimated it during sched_setattr().
310  */
311 static void replenish_dl_entity(struct sched_dl_entity *dl_se,
312 				struct sched_dl_entity *pi_se)
313 {
314 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
315 	struct rq *rq = rq_of_dl_rq(dl_rq);
316 
317 	BUG_ON(pi_se->dl_runtime <= 0);
318 
319 	/*
320 	 * This could be the case for a !-dl task that is boosted.
321 	 * Just go with full inherited parameters.
322 	 */
323 	if (dl_se->dl_deadline == 0) {
324 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
325 		dl_se->runtime = pi_se->dl_runtime;
326 	}
327 
328 	/*
329 	 * We keep moving the deadline away until we get some
330 	 * available runtime for the entity. This ensures correct
331 	 * handling of situations where the runtime overrun is
332 	 * arbitrary large.
333 	 */
334 	while (dl_se->runtime <= 0) {
335 		dl_se->deadline += pi_se->dl_period;
336 		dl_se->runtime += pi_se->dl_runtime;
337 	}
338 
339 	/*
340 	 * At this point, the deadline really should be "in
341 	 * the future" with respect to rq->clock. If it's
342 	 * not, we are, for some reason, lagging too much!
343 	 * Anyway, after having warn userspace abut that,
344 	 * we still try to keep the things running by
345 	 * resetting the deadline and the budget of the
346 	 * entity.
347 	 */
348 	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
349 		printk_deferred_once("sched: DL replenish lagged to much\n");
350 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
351 		dl_se->runtime = pi_se->dl_runtime;
352 	}
353 
354 	if (dl_se->dl_yielded)
355 		dl_se->dl_yielded = 0;
356 	if (dl_se->dl_throttled)
357 		dl_se->dl_throttled = 0;
358 }
359 
360 /*
361  * Here we check if --at time t-- an entity (which is probably being
362  * [re]activated or, in general, enqueued) can use its remaining runtime
363  * and its current deadline _without_ exceeding the bandwidth it is
364  * assigned (function returns true if it can't). We are in fact applying
365  * one of the CBS rules: when a task wakes up, if the residual runtime
366  * over residual deadline fits within the allocated bandwidth, then we
367  * can keep the current (absolute) deadline and residual budget without
368  * disrupting the schedulability of the system. Otherwise, we should
369  * refill the runtime and set the deadline a period in the future,
370  * because keeping the current (absolute) deadline of the task would
371  * result in breaking guarantees promised to other tasks (refer to
372  * Documentation/scheduler/sched-deadline.txt for more informations).
373  *
374  * This function returns true if:
375  *
376  *   runtime / (deadline - t) > dl_runtime / dl_period ,
377  *
378  * IOW we can't recycle current parameters.
379  *
380  * Notice that the bandwidth check is done against the period. For
381  * task with deadline equal to period this is the same of using
382  * dl_deadline instead of dl_period in the equation above.
383  */
384 static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
385 			       struct sched_dl_entity *pi_se, u64 t)
386 {
387 	u64 left, right;
388 
389 	/*
390 	 * left and right are the two sides of the equation above,
391 	 * after a bit of shuffling to use multiplications instead
392 	 * of divisions.
393 	 *
394 	 * Note that none of the time values involved in the two
395 	 * multiplications are absolute: dl_deadline and dl_runtime
396 	 * are the relative deadline and the maximum runtime of each
397 	 * instance, runtime is the runtime left for the last instance
398 	 * and (deadline - t), since t is rq->clock, is the time left
399 	 * to the (absolute) deadline. Even if overflowing the u64 type
400 	 * is very unlikely to occur in both cases, here we scale down
401 	 * as we want to avoid that risk at all. Scaling down by 10
402 	 * means that we reduce granularity to 1us. We are fine with it,
403 	 * since this is only a true/false check and, anyway, thinking
404 	 * of anything below microseconds resolution is actually fiction
405 	 * (but still we want to give the user that illusion >;).
406 	 */
407 	left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
408 	right = ((dl_se->deadline - t) >> DL_SCALE) *
409 		(pi_se->dl_runtime >> DL_SCALE);
410 
411 	return dl_time_before(right, left);
412 }
413 
414 /*
415  * When a -deadline entity is queued back on the runqueue, its runtime and
416  * deadline might need updating.
417  *
418  * The policy here is that we update the deadline of the entity only if:
419  *  - the current deadline is in the past,
420  *  - using the remaining runtime with the current deadline would make
421  *    the entity exceed its bandwidth.
422  */
423 static void update_dl_entity(struct sched_dl_entity *dl_se,
424 			     struct sched_dl_entity *pi_se)
425 {
426 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
427 	struct rq *rq = rq_of_dl_rq(dl_rq);
428 
429 	/*
430 	 * The arrival of a new instance needs special treatment, i.e.,
431 	 * the actual scheduling parameters have to be "renewed".
432 	 */
433 	if (dl_se->dl_new) {
434 		setup_new_dl_entity(dl_se, pi_se);
435 		return;
436 	}
437 
438 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
439 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
440 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
441 		dl_se->runtime = pi_se->dl_runtime;
442 	}
443 }
444 
445 /*
446  * If the entity depleted all its runtime, and if we want it to sleep
447  * while waiting for some new execution time to become available, we
448  * set the bandwidth enforcement timer to the replenishment instant
449  * and try to activate it.
450  *
451  * Notice that it is important for the caller to know if the timer
452  * actually started or not (i.e., the replenishment instant is in
453  * the future or in the past).
454  */
455 static int start_dl_timer(struct sched_dl_entity *dl_se, bool boosted)
456 {
457 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
458 	struct rq *rq = rq_of_dl_rq(dl_rq);
459 	ktime_t now, act;
460 	ktime_t soft, hard;
461 	unsigned long range;
462 	s64 delta;
463 
464 	if (boosted)
465 		return 0;
466 	/*
467 	 * We want the timer to fire at the deadline, but considering
468 	 * that it is actually coming from rq->clock and not from
469 	 * hrtimer's time base reading.
470 	 */
471 	act = ns_to_ktime(dl_se->deadline);
472 	now = hrtimer_cb_get_time(&dl_se->dl_timer);
473 	delta = ktime_to_ns(now) - rq_clock(rq);
474 	act = ktime_add_ns(act, delta);
475 
476 	/*
477 	 * If the expiry time already passed, e.g., because the value
478 	 * chosen as the deadline is too small, don't even try to
479 	 * start the timer in the past!
480 	 */
481 	if (ktime_us_delta(act, now) < 0)
482 		return 0;
483 
484 	hrtimer_set_expires(&dl_se->dl_timer, act);
485 
486 	soft = hrtimer_get_softexpires(&dl_se->dl_timer);
487 	hard = hrtimer_get_expires(&dl_se->dl_timer);
488 	range = ktime_to_ns(ktime_sub(hard, soft));
489 	__hrtimer_start_range_ns(&dl_se->dl_timer, soft,
490 				 range, HRTIMER_MODE_ABS, 0);
491 
492 	return hrtimer_active(&dl_se->dl_timer);
493 }
494 
495 /*
496  * This is the bandwidth enforcement timer callback. If here, we know
497  * a task is not on its dl_rq, since the fact that the timer was running
498  * means the task is throttled and needs a runtime replenishment.
499  *
500  * However, what we actually do depends on the fact the task is active,
501  * (it is on its rq) or has been removed from there by a call to
502  * dequeue_task_dl(). In the former case we must issue the runtime
503  * replenishment and add the task back to the dl_rq; in the latter, we just
504  * do nothing but clearing dl_throttled, so that runtime and deadline
505  * updating (and the queueing back to dl_rq) will be done by the
506  * next call to enqueue_task_dl().
507  */
508 static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
509 {
510 	struct sched_dl_entity *dl_se = container_of(timer,
511 						     struct sched_dl_entity,
512 						     dl_timer);
513 	struct task_struct *p = dl_task_of(dl_se);
514 	unsigned long flags;
515 	struct rq *rq;
516 
517 	rq = task_rq_lock(current, &flags);
518 
519 	/*
520 	 * We need to take care of several possible races here:
521 	 *
522 	 *   - the task might have changed its scheduling policy
523 	 *     to something different than SCHED_DEADLINE
524 	 *   - the task might have changed its reservation parameters
525 	 *     (through sched_setattr())
526 	 *   - the task might have been boosted by someone else and
527 	 *     might be in the boosting/deboosting path
528 	 *
529 	 * In all this cases we bail out, as the task is already
530 	 * in the runqueue or is going to be enqueued back anyway.
531 	 */
532 	if (!dl_task(p) || dl_se->dl_new ||
533 	    dl_se->dl_boosted || !dl_se->dl_throttled)
534 		goto unlock;
535 
536 	sched_clock_tick();
537 	update_rq_clock(rq);
538 
539 	/*
540 	 * If the throttle happened during sched-out; like:
541 	 *
542 	 *   schedule()
543 	 *     deactivate_task()
544 	 *       dequeue_task_dl()
545 	 *         update_curr_dl()
546 	 *           start_dl_timer()
547 	 *         __dequeue_task_dl()
548 	 *     prev->on_rq = 0;
549 	 *
550 	 * We can be both throttled and !queued. Replenish the counter
551 	 * but do not enqueue -- wait for our wakeup to do that.
552 	 */
553 	if (!task_on_rq_queued(p)) {
554 		replenish_dl_entity(dl_se, dl_se);
555 		goto unlock;
556 	}
557 
558 	enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
559 	if (dl_task(rq->curr))
560 		check_preempt_curr_dl(rq, p, 0);
561 	else
562 		resched_curr(rq);
563 #ifdef CONFIG_SMP
564 	/*
565 	 * Queueing this task back might have overloaded rq,
566 	 * check if we need to kick someone away.
567 	 */
568 	if (has_pushable_dl_tasks(rq))
569 		push_dl_task(rq);
570 #endif
571 unlock:
572 	task_rq_unlock(rq, current, &flags);
573 
574 	return HRTIMER_NORESTART;
575 }
576 
577 void init_dl_task_timer(struct sched_dl_entity *dl_se)
578 {
579 	struct hrtimer *timer = &dl_se->dl_timer;
580 
581 	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
582 	timer->function = dl_task_timer;
583 }
584 
585 static
586 int dl_runtime_exceeded(struct rq *rq, struct sched_dl_entity *dl_se)
587 {
588 	return (dl_se->runtime <= 0);
589 }
590 
591 extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
592 
593 /*
594  * Update the current task's runtime statistics (provided it is still
595  * a -deadline task and has not been removed from the dl_rq).
596  */
597 static void update_curr_dl(struct rq *rq)
598 {
599 	struct task_struct *curr = rq->curr;
600 	struct sched_dl_entity *dl_se = &curr->dl;
601 	u64 delta_exec;
602 
603 	if (!dl_task(curr) || !on_dl_rq(dl_se))
604 		return;
605 
606 	/*
607 	 * Consumed budget is computed considering the time as
608 	 * observed by schedulable tasks (excluding time spent
609 	 * in hardirq context, etc.). Deadlines are instead
610 	 * computed using hard walltime. This seems to be the more
611 	 * natural solution, but the full ramifications of this
612 	 * approach need further study.
613 	 */
614 	delta_exec = rq_clock_task(rq) - curr->se.exec_start;
615 	if (unlikely((s64)delta_exec <= 0))
616 		return;
617 
618 	schedstat_set(curr->se.statistics.exec_max,
619 		      max(curr->se.statistics.exec_max, delta_exec));
620 
621 	curr->se.sum_exec_runtime += delta_exec;
622 	account_group_exec_runtime(curr, delta_exec);
623 
624 	curr->se.exec_start = rq_clock_task(rq);
625 	cpuacct_charge(curr, delta_exec);
626 
627 	sched_rt_avg_update(rq, delta_exec);
628 
629 	dl_se->runtime -= dl_se->dl_yielded ? 0 : delta_exec;
630 	if (dl_runtime_exceeded(rq, dl_se)) {
631 		dl_se->dl_throttled = 1;
632 		__dequeue_task_dl(rq, curr, 0);
633 		if (unlikely(!start_dl_timer(dl_se, curr->dl.dl_boosted)))
634 			enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
635 
636 		if (!is_leftmost(curr, &rq->dl))
637 			resched_curr(rq);
638 	}
639 
640 	/*
641 	 * Because -- for now -- we share the rt bandwidth, we need to
642 	 * account our runtime there too, otherwise actual rt tasks
643 	 * would be able to exceed the shared quota.
644 	 *
645 	 * Account to the root rt group for now.
646 	 *
647 	 * The solution we're working towards is having the RT groups scheduled
648 	 * using deadline servers -- however there's a few nasties to figure
649 	 * out before that can happen.
650 	 */
651 	if (rt_bandwidth_enabled()) {
652 		struct rt_rq *rt_rq = &rq->rt;
653 
654 		raw_spin_lock(&rt_rq->rt_runtime_lock);
655 		/*
656 		 * We'll let actual RT tasks worry about the overflow here, we
657 		 * have our own CBS to keep us inline; only account when RT
658 		 * bandwidth is relevant.
659 		 */
660 		if (sched_rt_bandwidth_account(rt_rq))
661 			rt_rq->rt_time += delta_exec;
662 		raw_spin_unlock(&rt_rq->rt_runtime_lock);
663 	}
664 }
665 
666 #ifdef CONFIG_SMP
667 
668 static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu);
669 
670 static inline u64 next_deadline(struct rq *rq)
671 {
672 	struct task_struct *next = pick_next_earliest_dl_task(rq, rq->cpu);
673 
674 	if (next && dl_prio(next->prio))
675 		return next->dl.deadline;
676 	else
677 		return 0;
678 }
679 
680 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
681 {
682 	struct rq *rq = rq_of_dl_rq(dl_rq);
683 
684 	if (dl_rq->earliest_dl.curr == 0 ||
685 	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
686 		/*
687 		 * If the dl_rq had no -deadline tasks, or if the new task
688 		 * has shorter deadline than the current one on dl_rq, we
689 		 * know that the previous earliest becomes our next earliest,
690 		 * as the new task becomes the earliest itself.
691 		 */
692 		dl_rq->earliest_dl.next = dl_rq->earliest_dl.curr;
693 		dl_rq->earliest_dl.curr = deadline;
694 		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, 1);
695 	} else if (dl_rq->earliest_dl.next == 0 ||
696 		   dl_time_before(deadline, dl_rq->earliest_dl.next)) {
697 		/*
698 		 * On the other hand, if the new -deadline task has a
699 		 * a later deadline than the earliest one on dl_rq, but
700 		 * it is earlier than the next (if any), we must
701 		 * recompute the next-earliest.
702 		 */
703 		dl_rq->earliest_dl.next = next_deadline(rq);
704 	}
705 }
706 
707 static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
708 {
709 	struct rq *rq = rq_of_dl_rq(dl_rq);
710 
711 	/*
712 	 * Since we may have removed our earliest (and/or next earliest)
713 	 * task we must recompute them.
714 	 */
715 	if (!dl_rq->dl_nr_running) {
716 		dl_rq->earliest_dl.curr = 0;
717 		dl_rq->earliest_dl.next = 0;
718 		cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
719 	} else {
720 		struct rb_node *leftmost = dl_rq->rb_leftmost;
721 		struct sched_dl_entity *entry;
722 
723 		entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
724 		dl_rq->earliest_dl.curr = entry->deadline;
725 		dl_rq->earliest_dl.next = next_deadline(rq);
726 		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline, 1);
727 	}
728 }
729 
730 #else
731 
732 static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
733 static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
734 
735 #endif /* CONFIG_SMP */
736 
737 static inline
738 void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
739 {
740 	int prio = dl_task_of(dl_se)->prio;
741 	u64 deadline = dl_se->deadline;
742 
743 	WARN_ON(!dl_prio(prio));
744 	dl_rq->dl_nr_running++;
745 	add_nr_running(rq_of_dl_rq(dl_rq), 1);
746 
747 	inc_dl_deadline(dl_rq, deadline);
748 	inc_dl_migration(dl_se, dl_rq);
749 }
750 
751 static inline
752 void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
753 {
754 	int prio = dl_task_of(dl_se)->prio;
755 
756 	WARN_ON(!dl_prio(prio));
757 	WARN_ON(!dl_rq->dl_nr_running);
758 	dl_rq->dl_nr_running--;
759 	sub_nr_running(rq_of_dl_rq(dl_rq), 1);
760 
761 	dec_dl_deadline(dl_rq, dl_se->deadline);
762 	dec_dl_migration(dl_se, dl_rq);
763 }
764 
765 static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
766 {
767 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
768 	struct rb_node **link = &dl_rq->rb_root.rb_node;
769 	struct rb_node *parent = NULL;
770 	struct sched_dl_entity *entry;
771 	int leftmost = 1;
772 
773 	BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));
774 
775 	while (*link) {
776 		parent = *link;
777 		entry = rb_entry(parent, struct sched_dl_entity, rb_node);
778 		if (dl_time_before(dl_se->deadline, entry->deadline))
779 			link = &parent->rb_left;
780 		else {
781 			link = &parent->rb_right;
782 			leftmost = 0;
783 		}
784 	}
785 
786 	if (leftmost)
787 		dl_rq->rb_leftmost = &dl_se->rb_node;
788 
789 	rb_link_node(&dl_se->rb_node, parent, link);
790 	rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root);
791 
792 	inc_dl_tasks(dl_se, dl_rq);
793 }
794 
795 static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
796 {
797 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
798 
799 	if (RB_EMPTY_NODE(&dl_se->rb_node))
800 		return;
801 
802 	if (dl_rq->rb_leftmost == &dl_se->rb_node) {
803 		struct rb_node *next_node;
804 
805 		next_node = rb_next(&dl_se->rb_node);
806 		dl_rq->rb_leftmost = next_node;
807 	}
808 
809 	rb_erase(&dl_se->rb_node, &dl_rq->rb_root);
810 	RB_CLEAR_NODE(&dl_se->rb_node);
811 
812 	dec_dl_tasks(dl_se, dl_rq);
813 }
814 
815 static void
816 enqueue_dl_entity(struct sched_dl_entity *dl_se,
817 		  struct sched_dl_entity *pi_se, int flags)
818 {
819 	BUG_ON(on_dl_rq(dl_se));
820 
821 	/*
822 	 * If this is a wakeup or a new instance, the scheduling
823 	 * parameters of the task might need updating. Otherwise,
824 	 * we want a replenishment of its runtime.
825 	 */
826 	if (dl_se->dl_new || flags & ENQUEUE_WAKEUP)
827 		update_dl_entity(dl_se, pi_se);
828 	else if (flags & ENQUEUE_REPLENISH)
829 		replenish_dl_entity(dl_se, pi_se);
830 
831 	__enqueue_dl_entity(dl_se);
832 }
833 
834 static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
835 {
836 	__dequeue_dl_entity(dl_se);
837 }
838 
839 static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
840 {
841 	struct task_struct *pi_task = rt_mutex_get_top_task(p);
842 	struct sched_dl_entity *pi_se = &p->dl;
843 
844 	/*
845 	 * Use the scheduling parameters of the top pi-waiter
846 	 * task if we have one and its (relative) deadline is
847 	 * smaller than our one... OTW we keep our runtime and
848 	 * deadline.
849 	 */
850 	if (pi_task && p->dl.dl_boosted && dl_prio(pi_task->normal_prio)) {
851 		pi_se = &pi_task->dl;
852 	} else if (!dl_prio(p->normal_prio)) {
853 		/*
854 		 * Special case in which we have a !SCHED_DEADLINE task
855 		 * that is going to be deboosted, but exceedes its
856 		 * runtime while doing so. No point in replenishing
857 		 * it, as it's going to return back to its original
858 		 * scheduling class after this.
859 		 */
860 		BUG_ON(!p->dl.dl_boosted || flags != ENQUEUE_REPLENISH);
861 		return;
862 	}
863 
864 	/*
865 	 * If p is throttled, we do nothing. In fact, if it exhausted
866 	 * its budget it needs a replenishment and, since it now is on
867 	 * its rq, the bandwidth timer callback (which clearly has not
868 	 * run yet) will take care of this.
869 	 */
870 	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
871 		return;
872 
873 	enqueue_dl_entity(&p->dl, pi_se, flags);
874 
875 	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
876 		enqueue_pushable_dl_task(rq, p);
877 }
878 
879 static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
880 {
881 	dequeue_dl_entity(&p->dl);
882 	dequeue_pushable_dl_task(rq, p);
883 }
884 
885 static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
886 {
887 	update_curr_dl(rq);
888 	__dequeue_task_dl(rq, p, flags);
889 }
890 
891 /*
892  * Yield task semantic for -deadline tasks is:
893  *
894  *   get off from the CPU until our next instance, with
895  *   a new runtime. This is of little use now, since we
896  *   don't have a bandwidth reclaiming mechanism. Anyway,
897  *   bandwidth reclaiming is planned for the future, and
898  *   yield_task_dl will indicate that some spare budget
899  *   is available for other task instances to use it.
900  */
901 static void yield_task_dl(struct rq *rq)
902 {
903 	struct task_struct *p = rq->curr;
904 
905 	/*
906 	 * We make the task go to sleep until its current deadline by
907 	 * forcing its runtime to zero. This way, update_curr_dl() stops
908 	 * it and the bandwidth timer will wake it up and will give it
909 	 * new scheduling parameters (thanks to dl_yielded=1).
910 	 */
911 	if (p->dl.runtime > 0) {
912 		rq->curr->dl.dl_yielded = 1;
913 		p->dl.runtime = 0;
914 	}
915 	update_rq_clock(rq);
916 	update_curr_dl(rq);
917 }
918 
919 #ifdef CONFIG_SMP
920 
921 static int find_later_rq(struct task_struct *task);
922 
923 static int
924 select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
925 {
926 	struct task_struct *curr;
927 	struct rq *rq;
928 
929 	if (sd_flag != SD_BALANCE_WAKE)
930 		goto out;
931 
932 	rq = cpu_rq(cpu);
933 
934 	rcu_read_lock();
935 	curr = ACCESS_ONCE(rq->curr); /* unlocked access */
936 
937 	/*
938 	 * If we are dealing with a -deadline task, we must
939 	 * decide where to wake it up.
940 	 * If it has a later deadline and the current task
941 	 * on this rq can't move (provided the waking task
942 	 * can!) we prefer to send it somewhere else. On the
943 	 * other hand, if it has a shorter deadline, we
944 	 * try to make it stay here, it might be important.
945 	 */
946 	if (unlikely(dl_task(curr)) &&
947 	    (curr->nr_cpus_allowed < 2 ||
948 	     !dl_entity_preempt(&p->dl, &curr->dl)) &&
949 	    (p->nr_cpus_allowed > 1)) {
950 		int target = find_later_rq(p);
951 
952 		if (target != -1)
953 			cpu = target;
954 	}
955 	rcu_read_unlock();
956 
957 out:
958 	return cpu;
959 }
960 
961 static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
962 {
963 	/*
964 	 * Current can't be migrated, useless to reschedule,
965 	 * let's hope p can move out.
966 	 */
967 	if (rq->curr->nr_cpus_allowed == 1 ||
968 	    cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1)
969 		return;
970 
971 	/*
972 	 * p is migratable, so let's not schedule it and
973 	 * see if it is pushed or pulled somewhere else.
974 	 */
975 	if (p->nr_cpus_allowed != 1 &&
976 	    cpudl_find(&rq->rd->cpudl, p, NULL) != -1)
977 		return;
978 
979 	resched_curr(rq);
980 }
981 
982 static int pull_dl_task(struct rq *this_rq);
983 
984 #endif /* CONFIG_SMP */
985 
986 /*
987  * Only called when both the current and waking task are -deadline
988  * tasks.
989  */
990 static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
991 				  int flags)
992 {
993 	if (dl_entity_preempt(&p->dl, &rq->curr->dl)) {
994 		resched_curr(rq);
995 		return;
996 	}
997 
998 #ifdef CONFIG_SMP
999 	/*
1000 	 * In the unlikely case current and p have the same deadline
1001 	 * let us try to decide what's the best thing to do...
1002 	 */
1003 	if ((p->dl.deadline == rq->curr->dl.deadline) &&
1004 	    !test_tsk_need_resched(rq->curr))
1005 		check_preempt_equal_dl(rq, p);
1006 #endif /* CONFIG_SMP */
1007 }
1008 
1009 #ifdef CONFIG_SCHED_HRTICK
1010 static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1011 {
1012 	hrtick_start(rq, p->dl.runtime);
1013 }
1014 #else /* !CONFIG_SCHED_HRTICK */
1015 static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1016 {
1017 }
1018 #endif
1019 
1020 static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
1021 						   struct dl_rq *dl_rq)
1022 {
1023 	struct rb_node *left = dl_rq->rb_leftmost;
1024 
1025 	if (!left)
1026 		return NULL;
1027 
1028 	return rb_entry(left, struct sched_dl_entity, rb_node);
1029 }
1030 
1031 struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
1032 {
1033 	struct sched_dl_entity *dl_se;
1034 	struct task_struct *p;
1035 	struct dl_rq *dl_rq;
1036 
1037 	dl_rq = &rq->dl;
1038 
1039 	if (need_pull_dl_task(rq, prev)) {
1040 		pull_dl_task(rq);
1041 		/*
1042 		 * pull_rt_task() can drop (and re-acquire) rq->lock; this
1043 		 * means a stop task can slip in, in which case we need to
1044 		 * re-start task selection.
1045 		 */
1046 		if (rq->stop && task_on_rq_queued(rq->stop))
1047 			return RETRY_TASK;
1048 	}
1049 
1050 	/*
1051 	 * When prev is DL, we may throttle it in put_prev_task().
1052 	 * So, we update time before we check for dl_nr_running.
1053 	 */
1054 	if (prev->sched_class == &dl_sched_class)
1055 		update_curr_dl(rq);
1056 
1057 	if (unlikely(!dl_rq->dl_nr_running))
1058 		return NULL;
1059 
1060 	put_prev_task(rq, prev);
1061 
1062 	dl_se = pick_next_dl_entity(rq, dl_rq);
1063 	BUG_ON(!dl_se);
1064 
1065 	p = dl_task_of(dl_se);
1066 	p->se.exec_start = rq_clock_task(rq);
1067 
1068 	/* Running task will never be pushed. */
1069        dequeue_pushable_dl_task(rq, p);
1070 
1071 	if (hrtick_enabled(rq))
1072 		start_hrtick_dl(rq, p);
1073 
1074 	set_post_schedule(rq);
1075 
1076 	return p;
1077 }
1078 
1079 static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
1080 {
1081 	update_curr_dl(rq);
1082 
1083 	if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1)
1084 		enqueue_pushable_dl_task(rq, p);
1085 }
1086 
1087 static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
1088 {
1089 	update_curr_dl(rq);
1090 
1091 	/*
1092 	 * Even when we have runtime, update_curr_dl() might have resulted in us
1093 	 * not being the leftmost task anymore. In that case NEED_RESCHED will
1094 	 * be set and schedule() will start a new hrtick for the next task.
1095 	 */
1096 	if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
1097 	    is_leftmost(p, &rq->dl))
1098 		start_hrtick_dl(rq, p);
1099 }
1100 
1101 static void task_fork_dl(struct task_struct *p)
1102 {
1103 	/*
1104 	 * SCHED_DEADLINE tasks cannot fork and this is achieved through
1105 	 * sched_fork()
1106 	 */
1107 }
1108 
1109 static void task_dead_dl(struct task_struct *p)
1110 {
1111 	struct hrtimer *timer = &p->dl.dl_timer;
1112 	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
1113 
1114 	/*
1115 	 * Since we are TASK_DEAD we won't slip out of the domain!
1116 	 */
1117 	raw_spin_lock_irq(&dl_b->lock);
1118 	/* XXX we should retain the bw until 0-lag */
1119 	dl_b->total_bw -= p->dl.dl_bw;
1120 	raw_spin_unlock_irq(&dl_b->lock);
1121 
1122 	hrtimer_cancel(timer);
1123 }
1124 
1125 static void set_curr_task_dl(struct rq *rq)
1126 {
1127 	struct task_struct *p = rq->curr;
1128 
1129 	p->se.exec_start = rq_clock_task(rq);
1130 
1131 	/* You can't push away the running task */
1132 	dequeue_pushable_dl_task(rq, p);
1133 }
1134 
1135 #ifdef CONFIG_SMP
1136 
1137 /* Only try algorithms three times */
1138 #define DL_MAX_TRIES 3
1139 
1140 static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
1141 {
1142 	if (!task_running(rq, p) &&
1143 	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1144 		return 1;
1145 	return 0;
1146 }
1147 
1148 /* Returns the second earliest -deadline task, NULL otherwise */
1149 static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu)
1150 {
1151 	struct rb_node *next_node = rq->dl.rb_leftmost;
1152 	struct sched_dl_entity *dl_se;
1153 	struct task_struct *p = NULL;
1154 
1155 next_node:
1156 	next_node = rb_next(next_node);
1157 	if (next_node) {
1158 		dl_se = rb_entry(next_node, struct sched_dl_entity, rb_node);
1159 		p = dl_task_of(dl_se);
1160 
1161 		if (pick_dl_task(rq, p, cpu))
1162 			return p;
1163 
1164 		goto next_node;
1165 	}
1166 
1167 	return NULL;
1168 }
1169 
1170 static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
1171 
1172 static int find_later_rq(struct task_struct *task)
1173 {
1174 	struct sched_domain *sd;
1175 	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
1176 	int this_cpu = smp_processor_id();
1177 	int best_cpu, cpu = task_cpu(task);
1178 
1179 	/* Make sure the mask is initialized first */
1180 	if (unlikely(!later_mask))
1181 		return -1;
1182 
1183 	if (task->nr_cpus_allowed == 1)
1184 		return -1;
1185 
1186 	/*
1187 	 * We have to consider system topology and task affinity
1188 	 * first, then we can look for a suitable cpu.
1189 	 */
1190 	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
1191 			task, later_mask);
1192 	if (best_cpu == -1)
1193 		return -1;
1194 
1195 	/*
1196 	 * If we are here, some target has been found,
1197 	 * the most suitable of which is cached in best_cpu.
1198 	 * This is, among the runqueues where the current tasks
1199 	 * have later deadlines than the task's one, the rq
1200 	 * with the latest possible one.
1201 	 *
1202 	 * Now we check how well this matches with task's
1203 	 * affinity and system topology.
1204 	 *
1205 	 * The last cpu where the task run is our first
1206 	 * guess, since it is most likely cache-hot there.
1207 	 */
1208 	if (cpumask_test_cpu(cpu, later_mask))
1209 		return cpu;
1210 	/*
1211 	 * Check if this_cpu is to be skipped (i.e., it is
1212 	 * not in the mask) or not.
1213 	 */
1214 	if (!cpumask_test_cpu(this_cpu, later_mask))
1215 		this_cpu = -1;
1216 
1217 	rcu_read_lock();
1218 	for_each_domain(cpu, sd) {
1219 		if (sd->flags & SD_WAKE_AFFINE) {
1220 
1221 			/*
1222 			 * If possible, preempting this_cpu is
1223 			 * cheaper than migrating.
1224 			 */
1225 			if (this_cpu != -1 &&
1226 			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
1227 				rcu_read_unlock();
1228 				return this_cpu;
1229 			}
1230 
1231 			/*
1232 			 * Last chance: if best_cpu is valid and is
1233 			 * in the mask, that becomes our choice.
1234 			 */
1235 			if (best_cpu < nr_cpu_ids &&
1236 			    cpumask_test_cpu(best_cpu, sched_domain_span(sd))) {
1237 				rcu_read_unlock();
1238 				return best_cpu;
1239 			}
1240 		}
1241 	}
1242 	rcu_read_unlock();
1243 
1244 	/*
1245 	 * At this point, all our guesses failed, we just return
1246 	 * 'something', and let the caller sort the things out.
1247 	 */
1248 	if (this_cpu != -1)
1249 		return this_cpu;
1250 
1251 	cpu = cpumask_any(later_mask);
1252 	if (cpu < nr_cpu_ids)
1253 		return cpu;
1254 
1255 	return -1;
1256 }
1257 
1258 /* Locks the rq it finds */
1259 static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
1260 {
1261 	struct rq *later_rq = NULL;
1262 	int tries;
1263 	int cpu;
1264 
1265 	for (tries = 0; tries < DL_MAX_TRIES; tries++) {
1266 		cpu = find_later_rq(task);
1267 
1268 		if ((cpu == -1) || (cpu == rq->cpu))
1269 			break;
1270 
1271 		later_rq = cpu_rq(cpu);
1272 
1273 		/* Retry if something changed. */
1274 		if (double_lock_balance(rq, later_rq)) {
1275 			if (unlikely(task_rq(task) != rq ||
1276 				     !cpumask_test_cpu(later_rq->cpu,
1277 				                       &task->cpus_allowed) ||
1278 				     task_running(rq, task) ||
1279 				     !task_on_rq_queued(task))) {
1280 				double_unlock_balance(rq, later_rq);
1281 				later_rq = NULL;
1282 				break;
1283 			}
1284 		}
1285 
1286 		/*
1287 		 * If the rq we found has no -deadline task, or
1288 		 * its earliest one has a later deadline than our
1289 		 * task, the rq is a good one.
1290 		 */
1291 		if (!later_rq->dl.dl_nr_running ||
1292 		    dl_time_before(task->dl.deadline,
1293 				   later_rq->dl.earliest_dl.curr))
1294 			break;
1295 
1296 		/* Otherwise we try again. */
1297 		double_unlock_balance(rq, later_rq);
1298 		later_rq = NULL;
1299 	}
1300 
1301 	return later_rq;
1302 }
1303 
1304 static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
1305 {
1306 	struct task_struct *p;
1307 
1308 	if (!has_pushable_dl_tasks(rq))
1309 		return NULL;
1310 
1311 	p = rb_entry(rq->dl.pushable_dl_tasks_leftmost,
1312 		     struct task_struct, pushable_dl_tasks);
1313 
1314 	BUG_ON(rq->cpu != task_cpu(p));
1315 	BUG_ON(task_current(rq, p));
1316 	BUG_ON(p->nr_cpus_allowed <= 1);
1317 
1318 	BUG_ON(!task_on_rq_queued(p));
1319 	BUG_ON(!dl_task(p));
1320 
1321 	return p;
1322 }
1323 
1324 /*
1325  * See if the non running -deadline tasks on this rq
1326  * can be sent to some other CPU where they can preempt
1327  * and start executing.
1328  */
1329 static int push_dl_task(struct rq *rq)
1330 {
1331 	struct task_struct *next_task;
1332 	struct rq *later_rq;
1333 	int ret = 0;
1334 
1335 	if (!rq->dl.overloaded)
1336 		return 0;
1337 
1338 	next_task = pick_next_pushable_dl_task(rq);
1339 	if (!next_task)
1340 		return 0;
1341 
1342 retry:
1343 	if (unlikely(next_task == rq->curr)) {
1344 		WARN_ON(1);
1345 		return 0;
1346 	}
1347 
1348 	/*
1349 	 * If next_task preempts rq->curr, and rq->curr
1350 	 * can move away, it makes sense to just reschedule
1351 	 * without going further in pushing next_task.
1352 	 */
1353 	if (dl_task(rq->curr) &&
1354 	    dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&
1355 	    rq->curr->nr_cpus_allowed > 1) {
1356 		resched_curr(rq);
1357 		return 0;
1358 	}
1359 
1360 	/* We might release rq lock */
1361 	get_task_struct(next_task);
1362 
1363 	/* Will lock the rq it'll find */
1364 	later_rq = find_lock_later_rq(next_task, rq);
1365 	if (!later_rq) {
1366 		struct task_struct *task;
1367 
1368 		/*
1369 		 * We must check all this again, since
1370 		 * find_lock_later_rq releases rq->lock and it is
1371 		 * then possible that next_task has migrated.
1372 		 */
1373 		task = pick_next_pushable_dl_task(rq);
1374 		if (task_cpu(next_task) == rq->cpu && task == next_task) {
1375 			/*
1376 			 * The task is still there. We don't try
1377 			 * again, some other cpu will pull it when ready.
1378 			 */
1379 			goto out;
1380 		}
1381 
1382 		if (!task)
1383 			/* No more tasks */
1384 			goto out;
1385 
1386 		put_task_struct(next_task);
1387 		next_task = task;
1388 		goto retry;
1389 	}
1390 
1391 	deactivate_task(rq, next_task, 0);
1392 	set_task_cpu(next_task, later_rq->cpu);
1393 	activate_task(later_rq, next_task, 0);
1394 	ret = 1;
1395 
1396 	resched_curr(later_rq);
1397 
1398 	double_unlock_balance(rq, later_rq);
1399 
1400 out:
1401 	put_task_struct(next_task);
1402 
1403 	return ret;
1404 }
1405 
1406 static void push_dl_tasks(struct rq *rq)
1407 {
1408 	/* Terminates as it moves a -deadline task */
1409 	while (push_dl_task(rq))
1410 		;
1411 }
1412 
1413 static int pull_dl_task(struct rq *this_rq)
1414 {
1415 	int this_cpu = this_rq->cpu, ret = 0, cpu;
1416 	struct task_struct *p;
1417 	struct rq *src_rq;
1418 	u64 dmin = LONG_MAX;
1419 
1420 	if (likely(!dl_overloaded(this_rq)))
1421 		return 0;
1422 
1423 	/*
1424 	 * Match the barrier from dl_set_overloaded; this guarantees that if we
1425 	 * see overloaded we must also see the dlo_mask bit.
1426 	 */
1427 	smp_rmb();
1428 
1429 	for_each_cpu(cpu, this_rq->rd->dlo_mask) {
1430 		if (this_cpu == cpu)
1431 			continue;
1432 
1433 		src_rq = cpu_rq(cpu);
1434 
1435 		/*
1436 		 * It looks racy, abd it is! However, as in sched_rt.c,
1437 		 * we are fine with this.
1438 		 */
1439 		if (this_rq->dl.dl_nr_running &&
1440 		    dl_time_before(this_rq->dl.earliest_dl.curr,
1441 				   src_rq->dl.earliest_dl.next))
1442 			continue;
1443 
1444 		/* Might drop this_rq->lock */
1445 		double_lock_balance(this_rq, src_rq);
1446 
1447 		/*
1448 		 * If there are no more pullable tasks on the
1449 		 * rq, we're done with it.
1450 		 */
1451 		if (src_rq->dl.dl_nr_running <= 1)
1452 			goto skip;
1453 
1454 		p = pick_next_earliest_dl_task(src_rq, this_cpu);
1455 
1456 		/*
1457 		 * We found a task to be pulled if:
1458 		 *  - it preempts our current (if there's one),
1459 		 *  - it will preempt the last one we pulled (if any).
1460 		 */
1461 		if (p && dl_time_before(p->dl.deadline, dmin) &&
1462 		    (!this_rq->dl.dl_nr_running ||
1463 		     dl_time_before(p->dl.deadline,
1464 				    this_rq->dl.earliest_dl.curr))) {
1465 			WARN_ON(p == src_rq->curr);
1466 			WARN_ON(!task_on_rq_queued(p));
1467 
1468 			/*
1469 			 * Then we pull iff p has actually an earlier
1470 			 * deadline than the current task of its runqueue.
1471 			 */
1472 			if (dl_time_before(p->dl.deadline,
1473 					   src_rq->curr->dl.deadline))
1474 				goto skip;
1475 
1476 			ret = 1;
1477 
1478 			deactivate_task(src_rq, p, 0);
1479 			set_task_cpu(p, this_cpu);
1480 			activate_task(this_rq, p, 0);
1481 			dmin = p->dl.deadline;
1482 
1483 			/* Is there any other task even earlier? */
1484 		}
1485 skip:
1486 		double_unlock_balance(this_rq, src_rq);
1487 	}
1488 
1489 	return ret;
1490 }
1491 
1492 static void post_schedule_dl(struct rq *rq)
1493 {
1494 	push_dl_tasks(rq);
1495 }
1496 
1497 /*
1498  * Since the task is not running and a reschedule is not going to happen
1499  * anytime soon on its runqueue, we try pushing it away now.
1500  */
1501 static void task_woken_dl(struct rq *rq, struct task_struct *p)
1502 {
1503 	if (!task_running(rq, p) &&
1504 	    !test_tsk_need_resched(rq->curr) &&
1505 	    has_pushable_dl_tasks(rq) &&
1506 	    p->nr_cpus_allowed > 1 &&
1507 	    dl_task(rq->curr) &&
1508 	    (rq->curr->nr_cpus_allowed < 2 ||
1509 	     !dl_entity_preempt(&p->dl, &rq->curr->dl))) {
1510 		push_dl_tasks(rq);
1511 	}
1512 }
1513 
1514 static void set_cpus_allowed_dl(struct task_struct *p,
1515 				const struct cpumask *new_mask)
1516 {
1517 	struct rq *rq;
1518 	struct root_domain *src_rd;
1519 	int weight;
1520 
1521 	BUG_ON(!dl_task(p));
1522 
1523 	rq = task_rq(p);
1524 	src_rd = rq->rd;
1525 	/*
1526 	 * Migrating a SCHED_DEADLINE task between exclusive
1527 	 * cpusets (different root_domains) entails a bandwidth
1528 	 * update. We already made space for us in the destination
1529 	 * domain (see cpuset_can_attach()).
1530 	 */
1531 	if (!cpumask_intersects(src_rd->span, new_mask)) {
1532 		struct dl_bw *src_dl_b;
1533 
1534 		src_dl_b = dl_bw_of(cpu_of(rq));
1535 		/*
1536 		 * We now free resources of the root_domain we are migrating
1537 		 * off. In the worst case, sched_setattr() may temporary fail
1538 		 * until we complete the update.
1539 		 */
1540 		raw_spin_lock(&src_dl_b->lock);
1541 		__dl_clear(src_dl_b, p->dl.dl_bw);
1542 		raw_spin_unlock(&src_dl_b->lock);
1543 	}
1544 
1545 	/*
1546 	 * Update only if the task is actually running (i.e.,
1547 	 * it is on the rq AND it is not throttled).
1548 	 */
1549 	if (!on_dl_rq(&p->dl))
1550 		return;
1551 
1552 	weight = cpumask_weight(new_mask);
1553 
1554 	/*
1555 	 * Only update if the process changes its state from whether it
1556 	 * can migrate or not.
1557 	 */
1558 	if ((p->nr_cpus_allowed > 1) == (weight > 1))
1559 		return;
1560 
1561 	/*
1562 	 * The process used to be able to migrate OR it can now migrate
1563 	 */
1564 	if (weight <= 1) {
1565 		if (!task_current(rq, p))
1566 			dequeue_pushable_dl_task(rq, p);
1567 		BUG_ON(!rq->dl.dl_nr_migratory);
1568 		rq->dl.dl_nr_migratory--;
1569 	} else {
1570 		if (!task_current(rq, p))
1571 			enqueue_pushable_dl_task(rq, p);
1572 		rq->dl.dl_nr_migratory++;
1573 	}
1574 
1575 	update_dl_migration(&rq->dl);
1576 }
1577 
1578 /* Assumes rq->lock is held */
1579 static void rq_online_dl(struct rq *rq)
1580 {
1581 	if (rq->dl.overloaded)
1582 		dl_set_overload(rq);
1583 
1584 	cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
1585 	if (rq->dl.dl_nr_running > 0)
1586 		cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr, 1);
1587 }
1588 
1589 /* Assumes rq->lock is held */
1590 static void rq_offline_dl(struct rq *rq)
1591 {
1592 	if (rq->dl.overloaded)
1593 		dl_clear_overload(rq);
1594 
1595 	cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
1596 	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
1597 }
1598 
1599 void init_sched_dl_class(void)
1600 {
1601 	unsigned int i;
1602 
1603 	for_each_possible_cpu(i)
1604 		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
1605 					GFP_KERNEL, cpu_to_node(i));
1606 }
1607 
1608 #endif /* CONFIG_SMP */
1609 
1610 /*
1611  *  Ensure p's dl_timer is cancelled. May drop rq->lock for a while.
1612  */
1613 static void cancel_dl_timer(struct rq *rq, struct task_struct *p)
1614 {
1615 	struct hrtimer *dl_timer = &p->dl.dl_timer;
1616 
1617 	/* Nobody will change task's class if pi_lock is held */
1618 	lockdep_assert_held(&p->pi_lock);
1619 
1620 	if (hrtimer_active(dl_timer)) {
1621 		int ret = hrtimer_try_to_cancel(dl_timer);
1622 
1623 		if (unlikely(ret == -1)) {
1624 			/*
1625 			 * Note, p may migrate OR new deadline tasks
1626 			 * may appear in rq when we are unlocking it.
1627 			 * A caller of us must be fine with that.
1628 			 */
1629 			raw_spin_unlock(&rq->lock);
1630 			hrtimer_cancel(dl_timer);
1631 			raw_spin_lock(&rq->lock);
1632 		}
1633 	}
1634 }
1635 
1636 static void switched_from_dl(struct rq *rq, struct task_struct *p)
1637 {
1638 	/* XXX we should retain the bw until 0-lag */
1639 	cancel_dl_timer(rq, p);
1640 	__dl_clear_params(p);
1641 
1642 	/*
1643 	 * Since this might be the only -deadline task on the rq,
1644 	 * this is the right place to try to pull some other one
1645 	 * from an overloaded cpu, if any.
1646 	 */
1647 	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
1648 		return;
1649 
1650 	if (pull_dl_task(rq))
1651 		resched_curr(rq);
1652 }
1653 
1654 /*
1655  * When switching to -deadline, we may overload the rq, then
1656  * we try to push someone off, if possible.
1657  */
1658 static void switched_to_dl(struct rq *rq, struct task_struct *p)
1659 {
1660 	int check_resched = 1;
1661 
1662 	/*
1663 	 * If p is throttled, don't consider the possibility
1664 	 * of preempting rq->curr, the check will be done right
1665 	 * after its runtime will get replenished.
1666 	 */
1667 	if (unlikely(p->dl.dl_throttled))
1668 		return;
1669 
1670 	if (task_on_rq_queued(p) && rq->curr != p) {
1671 #ifdef CONFIG_SMP
1672 		if (p->nr_cpus_allowed > 1 && rq->dl.overloaded &&
1673 			push_dl_task(rq) && rq != task_rq(p))
1674 			/* Only reschedule if pushing failed */
1675 			check_resched = 0;
1676 #endif /* CONFIG_SMP */
1677 		if (check_resched) {
1678 			if (dl_task(rq->curr))
1679 				check_preempt_curr_dl(rq, p, 0);
1680 			else
1681 				resched_curr(rq);
1682 		}
1683 	}
1684 }
1685 
1686 /*
1687  * If the scheduling parameters of a -deadline task changed,
1688  * a push or pull operation might be needed.
1689  */
1690 static void prio_changed_dl(struct rq *rq, struct task_struct *p,
1691 			    int oldprio)
1692 {
1693 	if (task_on_rq_queued(p) || rq->curr == p) {
1694 #ifdef CONFIG_SMP
1695 		/*
1696 		 * This might be too much, but unfortunately
1697 		 * we don't have the old deadline value, and
1698 		 * we can't argue if the task is increasing
1699 		 * or lowering its prio, so...
1700 		 */
1701 		if (!rq->dl.overloaded)
1702 			pull_dl_task(rq);
1703 
1704 		/*
1705 		 * If we now have a earlier deadline task than p,
1706 		 * then reschedule, provided p is still on this
1707 		 * runqueue.
1708 		 */
1709 		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline) &&
1710 		    rq->curr == p)
1711 			resched_curr(rq);
1712 #else
1713 		/*
1714 		 * Again, we don't know if p has a earlier
1715 		 * or later deadline, so let's blindly set a
1716 		 * (maybe not needed) rescheduling point.
1717 		 */
1718 		resched_curr(rq);
1719 #endif /* CONFIG_SMP */
1720 	} else
1721 		switched_to_dl(rq, p);
1722 }
1723 
1724 const struct sched_class dl_sched_class = {
1725 	.next			= &rt_sched_class,
1726 	.enqueue_task		= enqueue_task_dl,
1727 	.dequeue_task		= dequeue_task_dl,
1728 	.yield_task		= yield_task_dl,
1729 
1730 	.check_preempt_curr	= check_preempt_curr_dl,
1731 
1732 	.pick_next_task		= pick_next_task_dl,
1733 	.put_prev_task		= put_prev_task_dl,
1734 
1735 #ifdef CONFIG_SMP
1736 	.select_task_rq		= select_task_rq_dl,
1737 	.set_cpus_allowed       = set_cpus_allowed_dl,
1738 	.rq_online              = rq_online_dl,
1739 	.rq_offline             = rq_offline_dl,
1740 	.post_schedule		= post_schedule_dl,
1741 	.task_woken		= task_woken_dl,
1742 #endif
1743 
1744 	.set_curr_task		= set_curr_task_dl,
1745 	.task_tick		= task_tick_dl,
1746 	.task_fork              = task_fork_dl,
1747 	.task_dead		= task_dead_dl,
1748 
1749 	.prio_changed           = prio_changed_dl,
1750 	.switched_from		= switched_from_dl,
1751 	.switched_to		= switched_to_dl,
1752 
1753 	.update_curr		= update_curr_dl,
1754 };
1755 
1756 #ifdef CONFIG_SCHED_DEBUG
1757 extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
1758 
1759 void print_dl_stats(struct seq_file *m, int cpu)
1760 {
1761 	print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
1762 }
1763 #endif /* CONFIG_SCHED_DEBUG */
1764