0001:   /*
0002:    * Deadline Scheduling Class (SCHED_DEADLINE)
0003:    *
0004:    * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
0005:    *
0006:    * Tasks that periodically executes their instances for less than their
0007:    * runtime won't miss any of their deadlines.
0008:    * Tasks that are not periodic or sporadic or that tries to execute more
0009:    * than their reserved bandwidth will be slowed down (and may potentially
0010:    * miss some of their deadlines), and won't affect any other task.
0011:    *
0012:    * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>,
0013:    *                    Juri Lelli <juri.lelli@gmail.com>,
0014:    *                    Michael Trimarchi <michael@amarulasolutions.com>,
0015:    *                    Fabio Checconi <fchecconi@gmail.com>
0016:    */
0017:   #include "sched.h"
0018:   
0019:   #include <linux/slab.h>
0020:   
0021:   struct dl_bandwidth def_dl_bandwidth;
0022:   
0023:   static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
0024:   {
0025:   	return container_of(dl_se, struct task_struct, dl);
0026:   }
0027:   
0028:   static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
0029:   {
0030:   	return container_of(dl_rq, struct rq, dl);
0031:   }
0032:   
0033:   static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
0034:   {
0035:   	struct task_struct *p = dl_task_of(dl_se);
0036:   	struct rq *rq = task_rq(p);
0037:   
0038:   	return &rq->dl;
0039:   }
0040:   
0041:   static inline int on_dl_rq(struct sched_dl_entity *dl_se)
0042:   {
0043:   	return !RB_EMPTY_NODE(&dl_se->rb_node);
0044:   }
0045:   
0046:   static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
0047:   {
0048:   	struct sched_dl_entity *dl_se = &p->dl;
0049:   
0050:   	return dl_rq->rb_leftmost == &dl_se->rb_node;
0051:   }
0052:   
0053:   void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
0054:   {
0055:   	raw_spin_lock_init(&dl_b->dl_runtime_lock);
0056:   	dl_b->dl_period = period;
0057:   	dl_b->dl_runtime = runtime;
0058:   }
0059:   
0060:   void init_dl_bw(struct dl_bw *dl_b)
0061:   {
0062:   	raw_spin_lock_init(&dl_b->lock);
0063:   	raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock);
0064:   	if (global_rt_runtime() == RUNTIME_INF)
0065:   		dl_b->bw = -1;
0066:   	else
0067:   		dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
0068:   	raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
0069:   	dl_b->total_bw = 0;
0070:   }
0071:   
0072:   void init_dl_rq(struct dl_rq *dl_rq)
0073:   {
0074:   	dl_rq->rb_root = RB_ROOT;
0075:   
0076:   #ifdef CONFIG_SMP
0077:   	/* zero means no -deadline tasks */
0078:   	dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;
0079:   
0080:   	dl_rq->dl_nr_migratory = 0;
0081:   	dl_rq->overloaded = 0;
0082:   	dl_rq->pushable_dl_tasks_root = RB_ROOT;
0083:   #else
0084:   	init_dl_bw(&dl_rq->dl_bw);
0085:   #endif
0086:   }
0087:   
0088:   #ifdef CONFIG_SMP
0089:   
0090:   static inline int dl_overloaded(struct rq *rq)
0091:   {
0092:   	return atomic_read(&rq->rd->dlo_count);
0093:   }
0094:   
0095:   static inline void dl_set_overload(struct rq *rq)
0096:   {
0097:   	if (!rq->online)
0098:   		return;
0099:   
0100:   	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
0101:   	/*
0102:   	 * Must be visible before the overload count is
0103:   	 * set (as in sched_rt.c).
0104:   	 *
0105:   	 * Matched by the barrier in pull_dl_task().
0106:   	 */
0107:   	smp_wmb();
0108:   	atomic_inc(&rq->rd->dlo_count);
0109:   }
0110:   
0111:   static inline void dl_clear_overload(struct rq *rq)
0112:   {
0113:   	if (!rq->online)
0114:   		return;
0115:   
0116:   	atomic_dec(&rq->rd->dlo_count);
0117:   	cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
0118:   }
0119:   
0120:   static void update_dl_migration(struct dl_rq *dl_rq)
0121:   {
0122:   	if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) {
0123:   		if (!dl_rq->overloaded) {
0124:   			dl_set_overload(rq_of_dl_rq(dl_rq));
0125:   			dl_rq->overloaded = 1;
0126:   		}
0127:   	} else if (dl_rq->overloaded) {
0128:   		dl_clear_overload(rq_of_dl_rq(dl_rq));
0129:   		dl_rq->overloaded = 0;
0130:   	}
0131:   }
0132:   
0133:   static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0134:   {
0135:   	struct task_struct *p = dl_task_of(dl_se);
0136:   
0137:   	if (p->nr_cpus_allowed > 1)
0138:   		dl_rq->dl_nr_migratory++;
0139:   
0140:   	update_dl_migration(dl_rq);
0141:   }
0142:   
0143:   static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0144:   {
0145:   	struct task_struct *p = dl_task_of(dl_se);
0146:   
0147:   	if (p->nr_cpus_allowed > 1)
0148:   		dl_rq->dl_nr_migratory--;
0149:   
0150:   	update_dl_migration(dl_rq);
0151:   }
0152:   
0153:   /*
0154:    * The list of pushable -deadline task is not a plist, like in
0155:    * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
0156:    */
0157:   static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
0158:   {
0159:   	struct dl_rq *dl_rq = &rq->dl;
0160:   	struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_node;
0161:   	struct rb_node *parent = NULL;
0162:   	struct task_struct *entry;
0163:   	int leftmost = 1;
0164:   
0165:   	BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
0166:   
0167:   	while (*link) {
0168:   		parent = *link;
0169:   		entry = rb_entry(parent, struct task_struct,
0170:   				 pushable_dl_tasks);
0171:   		if (dl_entity_preempt(&p->dl, &entry->dl))
0172:   			link = &parent->rb_left;
0173:   		else {
0174:   			link = &parent->rb_right;
0175:   			leftmost = 0;
0176:   		}
0177:   	}
0178:   
0179:   	if (leftmost)
0180:   		dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
0181:   
0182:   	rb_link_node(&p->pushable_dl_tasks, parent, link);
0183:   	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
0184:   }
0185:   
0186:   static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
0187:   {
0188:   	struct dl_rq *dl_rq = &rq->dl;
0189:   
0190:   	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
0191:   		return;
0192:   
0193:   	if (dl_rq->pushable_dl_tasks_leftmost == &p->pushable_dl_tasks) {
0194:   		struct rb_node *next_node;
0195:   
0196:   		next_node = rb_next(&p->pushable_dl_tasks);
0197:   		dl_rq->pushable_dl_tasks_leftmost = next_node;
0198:   	}
0199:   
0200:   	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
0201:   	RB_CLEAR_NODE(&p->pushable_dl_tasks);
0202:   }
0203:   
0204:   static inline int has_pushable_dl_tasks(struct rq *rq)
0205:   {
0206:   	return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
0207:   }
0208:   
0209:   static int push_dl_task(struct rq *rq);
0210:   
0211:   static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
0212:   {
0213:   	return dl_task(prev);
0214:   }
0215:   
0216:   static DEFINE_PER_CPU(struct callback_head, dl_push_head);
0217:   static DEFINE_PER_CPU(struct callback_head, dl_pull_head);
0218:   
0219:   static void push_dl_tasks(struct rq *);
0220:   static void pull_dl_task(struct rq *);
0221:   
0222:   static inline void queue_push_tasks(struct rq *rq)
0223:   {
0224:   	if (!has_pushable_dl_tasks(rq))
0225:   		return;
0226:   
0227:   	queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
0228:   }
0229:   
0230:   static inline void queue_pull_task(struct rq *rq)
0231:   {
0232:   	queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task);
0233:   }
0234:   
0235:   static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);
0236:   
0237:   static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p)
0238:   {
0239:   	struct rq *later_rq = NULL;
0240:   	bool fallback = false;
0241:   
0242:   	later_rq = find_lock_later_rq(p, rq);
0243:   
0244:   	if (!later_rq) {
0245:   		int cpu;
0246:   
0247:   		/*
0248:   		 * If we cannot preempt any rq, fall back to pick any
0249:   		 * online cpu.
0250:   		 */
0251:   		fallback = true;
0252:   		cpu = cpumask_any_and(cpu_active_mask, tsk_cpus_allowed(p));
0253:   		if (cpu >= nr_cpu_ids) {
0254:   			/*
0255:   			 * Fail to find any suitable cpu.
0256:   			 * The task will never come back!
0257:   			 */
0258:   			BUG_ON(dl_bandwidth_enabled());
0259:   
0260:   			/*
0261:   			 * If admission control is disabled we
0262:   			 * try a little harder to let the task
0263:   			 * run.
0264:   			 */
0265:   			cpu = cpumask_any(cpu_active_mask);
0266:   		}
0267:   		later_rq = cpu_rq(cpu);
0268:   		double_lock_balance(rq, later_rq);
0269:   	}
0270:   
0271:   	/*
0272:   	 * By now the task is replenished and enqueued; migrate it.
0273:   	 */
0274:   	deactivate_task(rq, p, 0);
0275:   	set_task_cpu(p, later_rq->cpu);
0276:   	activate_task(later_rq, p, 0);
0277:   
0278:   	if (!fallback)
0279:   		resched_curr(later_rq);
0280:   
0281:   	double_unlock_balance(later_rq, rq);
0282:   
0283:   	return later_rq;
0284:   }
0285:   
0286:   #else
0287:   
0288:   static inline
0289:   void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
0290:   {
0291:   }
0292:   
0293:   static inline
0294:   void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
0295:   {
0296:   }
0297:   
0298:   static inline
0299:   void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0300:   {
0301:   }
0302:   
0303:   static inline
0304:   void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0305:   {
0306:   }
0307:   
0308:   static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
0309:   {
0310:   	return false;
0311:   }
0312:   
0313:   static inline void pull_dl_task(struct rq *rq)
0314:   {
0315:   }
0316:   
0317:   static inline void queue_push_tasks(struct rq *rq)
0318:   {
0319:   }
0320:   
0321:   static inline void queue_pull_task(struct rq *rq)
0322:   {
0323:   }
0324:   #endif /* CONFIG_SMP */
0325:   
0326:   static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
0327:   static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags);
0328:   static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
0329:   				  int flags);
0330:   
0331:   /*
0332:    * We are being explicitly informed that a new instance is starting,
0333:    * and this means that:
0334:    *  - the absolute deadline of the entity has to be placed at
0335:    *    current time + relative deadline;
0336:    *  - the runtime of the entity has to be set to the maximum value.
0337:    *
0338:    * The capability of specifying such event is useful whenever a -deadline
0339:    * entity wants to (try to!) synchronize its behaviour with the scheduler's
0340:    * one, and to (try to!) reconcile itself with its own scheduling
0341:    * parameters.
0342:    */
0343:   static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se,
0344:   				       struct sched_dl_entity *pi_se)
0345:   {
0346:   	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
0347:   	struct rq *rq = rq_of_dl_rq(dl_rq);
0348:   
0349:   	WARN_ON(!dl_se->dl_new || dl_se->dl_throttled);
0350:   
0351:   	/*
0352:   	 * We use the regular wall clock time to set deadlines in the
0353:   	 * future; in fact, we must consider execution overheads (time
0354:   	 * spent on hardirq context, etc.).
0355:   	 */
0356:   	dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
0357:   	dl_se->runtime = pi_se->dl_runtime;
0358:   	dl_se->dl_new = 0;
0359:   }
0360:   
0361:   /*
0362:    * Pure Earliest Deadline First (EDF) scheduling does not deal with the
0363:    * possibility of a entity lasting more than what it declared, and thus
0364:    * exhausting its runtime.
0365:    *
0366:    * Here we are interested in making runtime overrun possible, but we do
0367:    * not want a entity which is misbehaving to affect the scheduling of all
0368:    * other entities.
0369:    * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
0370:    * is used, in order to confine each entity within its own bandwidth.
0371:    *
0372:    * This function deals exactly with that, and ensures that when the runtime
0373:    * of a entity is replenished, its deadline is also postponed. That ensures
0374:    * the overrunning entity can't interfere with other entity in the system and
0375:    * can't make them miss their deadlines. Reasons why this kind of overruns
0376:    * could happen are, typically, a entity voluntarily trying to overcome its
0377:    * runtime, or it just underestimated it during sched_setattr().
0378:    */
0379:   static void replenish_dl_entity(struct sched_dl_entity *dl_se,
0380:   				struct sched_dl_entity *pi_se)
0381:   {
0382:   	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
0383:   	struct rq *rq = rq_of_dl_rq(dl_rq);
0384:   
0385:   	BUG_ON(pi_se->dl_runtime <= 0);
0386:   
0387:   	/*
0388:   	 * This could be the case for a !-dl task that is boosted.
0389:   	 * Just go with full inherited parameters.
0390:   	 */
0391:   	if (dl_se->dl_deadline == 0) {
0392:   		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
0393:   		dl_se->runtime = pi_se->dl_runtime;
0394:   	}
0395:   
0396:   	/*
0397:   	 * We keep moving the deadline away until we get some
0398:   	 * available runtime for the entity. This ensures correct
0399:   	 * handling of situations where the runtime overrun is
0400:   	 * arbitrary large.
0401:   	 */
0402:   	while (dl_se->runtime <= 0) {
0403:   		dl_se->deadline += pi_se->dl_period;
0404:   		dl_se->runtime += pi_se->dl_runtime;
0405:   	}
0406:   
0407:   	/*
0408:   	 * At this point, the deadline really should be "in
0409:   	 * the future" with respect to rq->clock. If it's
0410:   	 * not, we are, for some reason, lagging too much!
0411:   	 * Anyway, after having warn userspace abut that,
0412:   	 * we still try to keep the things running by
0413:   	 * resetting the deadline and the budget of the
0414:   	 * entity.
0415:   	 */
0416:   	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
0417:   		printk_deferred_once("sched: DL replenish lagged to much\n");
0418:   		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
0419:   		dl_se->runtime = pi_se->dl_runtime;
0420:   	}
0421:   
0422:   	if (dl_se->dl_yielded)
0423:   		dl_se->dl_yielded = 0;
0424:   	if (dl_se->dl_throttled)
0425:   		dl_se->dl_throttled = 0;
0426:   }
0427:   
0428:   /*
0429:    * Here we check if --at time t-- an entity (which is probably being
0430:    * [re]activated or, in general, enqueued) can use its remaining runtime
0431:    * and its current deadline _without_ exceeding the bandwidth it is
0432:    * assigned (function returns true if it can't). We are in fact applying
0433:    * one of the CBS rules: when a task wakes up, if the residual runtime
0434:    * over residual deadline fits within the allocated bandwidth, then we
0435:    * can keep the current (absolute) deadline and residual budget without
0436:    * disrupting the schedulability of the system. Otherwise, we should
0437:    * refill the runtime and set the deadline a period in the future,
0438:    * because keeping the current (absolute) deadline of the task would
0439:    * result in breaking guarantees promised to other tasks (refer to
0440:    * Documentation/scheduler/sched-deadline.txt for more informations).
0441:    *
0442:    * This function returns true if:
0443:    *
0444:    *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
0445:    *
0446:    * IOW we can't recycle current parameters.
0447:    *
0448:    * Notice that the bandwidth check is done against the deadline. For
0449:    * task with deadline equal to period this is the same of using
0450:    * dl_period instead of dl_deadline in the equation above.
0451:    */
0452:   static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
0453:   			       struct sched_dl_entity *pi_se, u64 t)
0454:   {
0455:   	u64 left, right;
0456:   
0457:   	/*
0458:   	 * left and right are the two sides of the equation above,
0459:   	 * after a bit of shuffling to use multiplications instead
0460:   	 * of divisions.
0461:   	 *
0462:   	 * Note that none of the time values involved in the two
0463:   	 * multiplications are absolute: dl_deadline and dl_runtime
0464:   	 * are the relative deadline and the maximum runtime of each
0465:   	 * instance, runtime is the runtime left for the last instance
0466:   	 * and (deadline - t), since t is rq->clock, is the time left
0467:   	 * to the (absolute) deadline. Even if overflowing the u64 type
0468:   	 * is very unlikely to occur in both cases, here we scale down
0469:   	 * as we want to avoid that risk at all. Scaling down by 10
0470:   	 * means that we reduce granularity to 1us. We are fine with it,
0471:   	 * since this is only a true/false check and, anyway, thinking
0472:   	 * of anything below microseconds resolution is actually fiction
0473:   	 * (but still we want to give the user that illusion >;).
0474:   	 */
0475:   	left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
0476:   	right = ((dl_se->deadline - t) >> DL_SCALE) *
0477:   		(pi_se->dl_runtime >> DL_SCALE);
0478:   
0479:   	return dl_time_before(right, left);
0480:   }
0481:   
0482:   /*
0483:    * Revised wakeup rule [1]: For self-suspending tasks, rather then
0484:    * re-initializing task's runtime and deadline, the revised wakeup
0485:    * rule adjusts the task's runtime to avoid the task to overrun its
0486:    * density.
0487:    *
0488:    * Reasoning: a task may overrun the density if:
0489:    *    runtime / (deadline - t) > dl_runtime / dl_deadline
0490:    *
0491:    * Therefore, runtime can be adjusted to:
0492:    *     runtime = (dl_runtime / dl_deadline) * (deadline - t)
0493:    *
0494:    * In such way that runtime will be equal to the maximum density
0495:    * the task can use without breaking any rule.
0496:    *
0497:    * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant
0498:    * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24.
0499:    */
0500:   static void
0501:   update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq)
0502:   {
0503:   	u64 laxity = dl_se->deadline - rq_clock(rq);
0504:   
0505:   	/*
0506:   	 * If the task has deadline < period, and the deadline is in the past,
0507:   	 * it should already be throttled before this check.
0508:   	 *
0509:   	 * See update_dl_entity() comments for further details.
0510:   	 */
0511:   	WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq)));
0512:   
0513:   	dl_se->runtime = (dl_se->dl_density * laxity) >> 20;
0514:   }
0515:   
0516:   /*
0517:    * Regarding the deadline, a task with implicit deadline has a relative
0518:    * deadline == relative period. A task with constrained deadline has a
0519:    * relative deadline <= relative period.
0520:    *
0521:    * We support constrained deadline tasks. However, there are some restrictions
0522:    * applied only for tasks which do not have an implicit deadline. See
0523:    * update_dl_entity() to know more about such restrictions.
0524:    *
0525:    * The dl_is_implicit() returns true if the task has an implicit deadline.
0526:    */
0527:   static inline bool dl_is_implicit(struct sched_dl_entity *dl_se)
0528:   {
0529:   	return dl_se->dl_deadline == dl_se->dl_period;
0530:   }
0531:   
0532:   /*
0533:    * When a deadline entity is placed in the runqueue, its runtime and deadline
0534:    * might need to be updated. This is done by a CBS wake up rule. There are two
0535:    * different rules: 1) the original CBS; and 2) the Revisited CBS.
0536:    *
0537:    * When the task is starting a new period, the Original CBS is used. In this
0538:    * case, the runtime is replenished and a new absolute deadline is set.
0539:    *
0540:    * When a task is queued before the begin of the next period, using the
0541:    * remaining runtime and deadline could make the entity to overflow, see
0542:    * dl_entity_overflow() to find more about runtime overflow. When such case
0543:    * is detected, the runtime and deadline need to be updated.
0544:    *
0545:    * If the task has an implicit deadline, i.e., deadline == period, the Original
0546:    * CBS is applied. the runtime is replenished and a new absolute deadline is
0547:    * set, as in the previous cases.
0548:    *
0549:    * However, the Original CBS does not work properly for tasks with
0550:    * deadline < period, which are said to have a constrained deadline. By
0551:    * applying the Original CBS, a constrained deadline task would be able to run
0552:    * runtime/deadline in a period. With deadline < period, the task would
0553:    * overrun the runtime/period allowed bandwidth, breaking the admission test.
0554:    *
0555:    * In order to prevent this misbehave, the Revisited CBS is used for
0556:    * constrained deadline tasks when a runtime overflow is detected. In the
0557:    * Revisited CBS, rather than replenishing & setting a new absolute deadline,
0558:    * the remaining runtime of the task is reduced to avoid runtime overflow.
0559:    * Please refer to the comments update_dl_revised_wakeup() function to find
0560:    * more about the Revised CBS rule.
0561:    */
0562:   static void update_dl_entity(struct sched_dl_entity *dl_se,
0563:   			     struct sched_dl_entity *pi_se)
0564:   {
0565:   	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
0566:   	struct rq *rq = rq_of_dl_rq(dl_rq);
0567:   
0568:   	/*
0569:   	 * The arrival of a new instance needs special treatment, i.e.,
0570:   	 * the actual scheduling parameters have to be "renewed".
0571:   	 */
0572:   	if (dl_se->dl_new) {
0573:   		setup_new_dl_entity(dl_se, pi_se);
0574:   		return;
0575:   	}
0576:   
0577:   	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
0578:   	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
0579:   
0580:   		if (unlikely(!dl_is_implicit(dl_se) &&
0581:   			     !dl_time_before(dl_se->deadline, rq_clock(rq)) &&
0582:   			     !dl_se->dl_boosted)){
0583:   			update_dl_revised_wakeup(dl_se, rq);
0584:   			return;
0585:   		}
0586:   
0587:   		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
0588:   		dl_se->runtime = pi_se->dl_runtime;
0589:   	}
0590:   }
0591:   
0592:   static inline u64 dl_next_period(struct sched_dl_entity *dl_se)
0593:   {
0594:   	return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period;
0595:   }
0596:   
0597:   /*
0598:    * If the entity depleted all its runtime, and if we want it to sleep
0599:    * while waiting for some new execution time to become available, we
0600:    * set the bandwidth replenishment timer to the replenishment instant
0601:    * and try to activate it.
0602:    *
0603:    * Notice that it is important for the caller to know if the timer
0604:    * actually started or not (i.e., the replenishment instant is in
0605:    * the future or in the past).
0606:    */
0607:   static int start_dl_timer(struct task_struct *p)
0608:   {
0609:   	struct sched_dl_entity *dl_se = &p->dl;
0610:   	struct hrtimer *timer = &dl_se->dl_timer;
0611:   	struct rq *rq = task_rq(p);
0612:   	ktime_t now, act;
0613:   	s64 delta;
0614:   
0615:   	lockdep_assert_held(&rq->lock);
0616:   
0617:   	/*
0618:   	 * We want the timer to fire at the deadline, but considering
0619:   	 * that it is actually coming from rq->clock and not from
0620:   	 * hrtimer's time base reading.
0621:   	 */
0622:   	act = ns_to_ktime(dl_next_period(dl_se));
0623:   	now = hrtimer_cb_get_time(timer);
0624:   	delta = ktime_to_ns(now) - rq_clock(rq);
0625:   	act = ktime_add_ns(act, delta);
0626:   
0627:   	/*
0628:   	 * If the expiry time already passed, e.g., because the value
0629:   	 * chosen as the deadline is too small, don't even try to
0630:   	 * start the timer in the past!
0631:   	 */
0632:   	if (ktime_us_delta(act, now) < 0)
0633:   		return 0;
0634:   
0635:   	/*
0636:   	 * !enqueued will guarantee another callback; even if one is already in
0637:   	 * progress. This ensures a balanced {get,put}_task_struct().
0638:   	 *
0639:   	 * The race against __run_timer() clearing the enqueued state is
0640:   	 * harmless because we're holding task_rq()->lock, therefore the timer
0641:   	 * expiring after we've done the check will wait on its task_rq_lock()
0642:   	 * and observe our state.
0643:   	 */
0644:   	if (!hrtimer_is_queued(timer)) {
0645:   		get_task_struct(p);
0646:   		hrtimer_start(timer, act, HRTIMER_MODE_ABS);
0647:   	}
0648:   
0649:   	return 1;
0650:   }
0651:   
0652:   /*
0653:    * This is the bandwidth enforcement timer callback. If here, we know
0654:    * a task is not on its dl_rq, since the fact that the timer was running
0655:    * means the task is throttled and needs a runtime replenishment.
0656:    *
0657:    * However, what we actually do depends on the fact the task is active,
0658:    * (it is on its rq) or has been removed from there by a call to
0659:    * dequeue_task_dl(). In the former case we must issue the runtime
0660:    * replenishment and add the task back to the dl_rq; in the latter, we just
0661:    * do nothing but clearing dl_throttled, so that runtime and deadline
0662:    * updating (and the queueing back to dl_rq) will be done by the
0663:    * next call to enqueue_task_dl().
0664:    */
0665:   static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
0666:   {
0667:   	struct sched_dl_entity *dl_se = container_of(timer,
0668:   						     struct sched_dl_entity,
0669:   						     dl_timer);
0670:   	struct task_struct *p = dl_task_of(dl_se);
0671:   	unsigned long flags;
0672:   	struct rq *rq;
0673:   
0674:   	rq = task_rq_lock(p, &flags);
0675:   
0676:   	/*
0677:   	 * The task might have changed its scheduling policy to something
0678:   	 * different than SCHED_DEADLINE (through switched_fromd_dl()).
0679:   	 */
0680:   	if (!dl_task(p)) {
0681:   		__dl_clear_params(p);
0682:   		goto unlock;
0683:   	}
0684:   
0685:   	/*
0686:   	 * This is possible if switched_from_dl() raced against a running
0687:   	 * callback that took the above !dl_task() path and we've since then
0688:   	 * switched back into SCHED_DEADLINE.
0689:   	 *
0690:   	 * There's nothing to do except drop our task reference.
0691:   	 */
0692:   	if (dl_se->dl_new)
0693:   		goto unlock;
0694:   
0695:   	/*
0696:   	 * The task might have been boosted by someone else and might be in the
0697:   	 * boosting/deboosting path, its not throttled.
0698:   	 */
0699:   	if (dl_se->dl_boosted)
0700:   		goto unlock;
0701:   
0702:   	/*
0703:   	 * Spurious timer due to start_dl_timer() race; or we already received
0704:   	 * a replenishment from rt_mutex_setprio().
0705:   	 */
0706:   	if (!dl_se->dl_throttled)
0707:   		goto unlock;
0708:   
0709:   	sched_clock_tick();
0710:   	update_rq_clock(rq);
0711:   
0712:   	/*
0713:   	 * If the throttle happened during sched-out; like:
0714:   	 *
0715:   	 *   schedule()
0716:   	 *     deactivate_task()
0717:   	 *       dequeue_task_dl()
0718:   	 *         update_curr_dl()
0719:   	 *           start_dl_timer()
0720:   	 *         __dequeue_task_dl()
0721:   	 *     prev->on_rq = 0;
0722:   	 *
0723:   	 * We can be both throttled and !queued. Replenish the counter
0724:   	 * but do not enqueue -- wait for our wakeup to do that.
0725:   	 */
0726:   	if (!task_on_rq_queued(p)) {
0727:   		replenish_dl_entity(dl_se, dl_se);
0728:   		goto unlock;
0729:   	}
0730:   
0731:   	enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
0732:   	if (dl_task(rq->curr))
0733:   		check_preempt_curr_dl(rq, p, 0);
0734:   	else
0735:   		resched_curr(rq);
0736:   
0737:   #ifdef CONFIG_SMP
0738:   	/*
0739:   	 * Perform balancing operations here; after the replenishments.  We
0740:   	 * cannot drop rq->lock before this, otherwise the assertion in
0741:   	 * start_dl_timer() about not missing updates is not true.
0742:   	 *
0743:   	 * If we find that the rq the task was on is no longer available, we
0744:   	 * need to select a new rq.
0745:   	 *
0746:   	 * XXX figure out if select_task_rq_dl() deals with offline cpus.
0747:   	 */
0748:   	if (unlikely(!rq->online))
0749:   		rq = dl_task_offline_migration(rq, p);
0750:   
0751:   	/*
0752:   	 * Queueing this task back might have overloaded rq, check if we need
0753:   	 * to kick someone away.
0754:   	 */
0755:   	if (has_pushable_dl_tasks(rq)) {
0756:   		/*
0757:   		 * Nothing relies on rq->lock after this, so its safe to drop
0758:   		 * rq->lock.
0759:   		 */
0760:   		lockdep_unpin_lock(&rq->lock);
0761:   		push_dl_task(rq);
0762:   		lockdep_pin_lock(&rq->lock);
0763:   	}
0764:   #endif
0765:   
0766:   unlock:
0767:   	task_rq_unlock(rq, p, &flags);
0768:   
0769:   	/*
0770:   	 * This can free the task_struct, including this hrtimer, do not touch
0771:   	 * anything related to that after this.
0772:   	 */
0773:   	put_task_struct(p);
0774:   
0775:   	return HRTIMER_NORESTART;
0776:   }
0777:   
0778:   void init_dl_task_timer(struct sched_dl_entity *dl_se)
0779:   {
0780:   	struct hrtimer *timer = &dl_se->dl_timer;
0781:   
0782:   	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
0783:   	timer->function = dl_task_timer;
0784:   }
0785:   
0786:   /*
0787:    * During the activation, CBS checks if it can reuse the current task's
0788:    * runtime and period. If the deadline of the task is in the past, CBS
0789:    * cannot use the runtime, and so it replenishes the task. This rule
0790:    * works fine for implicit deadline tasks (deadline == period), and the
0791:    * CBS was designed for implicit deadline tasks. However, a task with
0792:    * constrained deadline (deadine < period) might be awakened after the
0793:    * deadline, but before the next period. In this case, replenishing the
0794:    * task would allow it to run for runtime / deadline. As in this case
0795:    * deadline < period, CBS enables a task to run for more than the
0796:    * runtime / period. In a very loaded system, this can cause a domino
0797:    * effect, making other tasks miss their deadlines.
0798:    *
0799:    * To avoid this problem, in the activation of a constrained deadline
0800:    * task after the deadline but before the next period, throttle the
0801:    * task and set the replenishing timer to the begin of the next period,
0802:    * unless it is boosted.
0803:    */
0804:   static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
0805:   {
0806:   	struct task_struct *p = dl_task_of(dl_se);
0807:   	struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
0808:   
0809:   	if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
0810:   	    dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
0811:   		if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
0812:   			return;
0813:   		dl_se->dl_throttled = 1;
0814:   		if (dl_se->runtime > 0)
0815:   			dl_se->runtime = 0;
0816:   	}
0817:   }
0818:   
0819:   static
0820:   int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
0821:   {
0822:   	return (dl_se->runtime <= 0);
0823:   }
0824:   
0825:   extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
0826:   
0827:   /*
0828:    * Update the current task's runtime statistics (provided it is still
0829:    * a -deadline task and has not been removed from the dl_rq).
0830:    */
0831:   static void update_curr_dl(struct rq *rq)
0832:   {
0833:   	struct task_struct *curr = rq->curr;
0834:   	struct sched_dl_entity *dl_se = &curr->dl;
0835:   	u64 delta_exec;
0836:   
0837:   	if (!dl_task(curr) || !on_dl_rq(dl_se))
0838:   		return;
0839:   
0840:   	/*
0841:   	 * Consumed budget is computed considering the time as
0842:   	 * observed by schedulable tasks (excluding time spent
0843:   	 * in hardirq context, etc.). Deadlines are instead
0844:   	 * computed using hard walltime. This seems to be the more
0845:   	 * natural solution, but the full ramifications of this
0846:   	 * approach need further study.
0847:   	 */
0848:   	delta_exec = rq_clock_task(rq) - curr->se.exec_start;
0849:   	if (unlikely((s64)delta_exec <= 0))
0850:   		return;
0851:   
0852:   	schedstat_set(curr->se.statistics.exec_max,
0853:   		      max(curr->se.statistics.exec_max, delta_exec));
0854:   
0855:   	curr->se.sum_exec_runtime += delta_exec;
0856:   	account_group_exec_runtime(curr, delta_exec);
0857:   
0858:   	curr->se.exec_start = rq_clock_task(rq);
0859:   	cpuacct_charge(curr, delta_exec);
0860:   
0861:   	sched_rt_avg_update(rq, delta_exec);
0862:   
0863:   	dl_se->runtime -= dl_se->dl_yielded ? 0 : delta_exec;
0864:   	if (dl_runtime_exceeded(dl_se)) {
0865:   		dl_se->dl_throttled = 1;
0866:   		__dequeue_task_dl(rq, curr, 0);
0867:   		if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
0868:   			enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
0869:   
0870:   		if (!is_leftmost(curr, &rq->dl))
0871:   			resched_curr(rq);
0872:   	}
0873:   
0874:   	/*
0875:   	 * Because -- for now -- we share the rt bandwidth, we need to
0876:   	 * account our runtime there too, otherwise actual rt tasks
0877:   	 * would be able to exceed the shared quota.
0878:   	 *
0879:   	 * Account to the root rt group for now.
0880:   	 *
0881:   	 * The solution we're working towards is having the RT groups scheduled
0882:   	 * using deadline servers -- however there's a few nasties to figure
0883:   	 * out before that can happen.
0884:   	 */
0885:   	if (rt_bandwidth_enabled()) {
0886:   		struct rt_rq *rt_rq = &rq->rt;
0887:   
0888:   		raw_spin_lock(&rt_rq->rt_runtime_lock);
0889:   		/*
0890:   		 * We'll let actual RT tasks worry about the overflow here, we
0891:   		 * have our own CBS to keep us inline; only account when RT
0892:   		 * bandwidth is relevant.
0893:   		 */
0894:   		if (sched_rt_bandwidth_account(rt_rq))
0895:   			rt_rq->rt_time += delta_exec;
0896:   		raw_spin_unlock(&rt_rq->rt_runtime_lock);
0897:   	}
0898:   }
0899:   
0900:   #ifdef CONFIG_SMP
0901:   
0902:   static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu);
0903:   
0904:   static inline u64 next_deadline(struct rq *rq)
0905:   {
0906:   	struct task_struct *next = pick_next_earliest_dl_task(rq, rq->cpu);
0907:   
0908:   	if (next && dl_prio(next->prio))
0909:   		return next->dl.deadline;
0910:   	else
0911:   		return 0;
0912:   }
0913:   
0914:   static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
0915:   {
0916:   	struct rq *rq = rq_of_dl_rq(dl_rq);
0917:   
0918:   	if (dl_rq->earliest_dl.curr == 0 ||
0919:   	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
0920:   		/*
0921:   		 * If the dl_rq had no -deadline tasks, or if the new task
0922:   		 * has shorter deadline than the current one on dl_rq, we
0923:   		 * know that the previous earliest becomes our next earliest,
0924:   		 * as the new task becomes the earliest itself.
0925:   		 */
0926:   		dl_rq->earliest_dl.next = dl_rq->earliest_dl.curr;
0927:   		dl_rq->earliest_dl.curr = deadline;
0928:   		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, 1);
0929:   	} else if (dl_rq->earliest_dl.next == 0 ||
0930:   		   dl_time_before(deadline, dl_rq->earliest_dl.next)) {
0931:   		/*
0932:   		 * On the other hand, if the new -deadline task has a
0933:   		 * a later deadline than the earliest one on dl_rq, but
0934:   		 * it is earlier than the next (if any), we must
0935:   		 * recompute the next-earliest.
0936:   		 */
0937:   		dl_rq->earliest_dl.next = next_deadline(rq);
0938:   	}
0939:   }
0940:   
0941:   static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
0942:   {
0943:   	struct rq *rq = rq_of_dl_rq(dl_rq);
0944:   
0945:   	/*
0946:   	 * Since we may have removed our earliest (and/or next earliest)
0947:   	 * task we must recompute them.
0948:   	 */
0949:   	if (!dl_rq->dl_nr_running) {
0950:   		dl_rq->earliest_dl.curr = 0;
0951:   		dl_rq->earliest_dl.next = 0;
0952:   		cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
0953:   	} else {
0954:   		struct rb_node *leftmost = dl_rq->rb_leftmost;
0955:   		struct sched_dl_entity *entry;
0956:   
0957:   		entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
0958:   		dl_rq->earliest_dl.curr = entry->deadline;
0959:   		dl_rq->earliest_dl.next = next_deadline(rq);
0960:   		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline, 1);
0961:   	}
0962:   }
0963:   
0964:   #else
0965:   
0966:   static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
0967:   static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
0968:   
0969:   #endif /* CONFIG_SMP */
0970:   
0971:   static inline
0972:   void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0973:   {
0974:   	int prio = dl_task_of(dl_se)->prio;
0975:   	u64 deadline = dl_se->deadline;
0976:   
0977:   	WARN_ON(!dl_prio(prio));
0978:   	dl_rq->dl_nr_running++;
0979:   	add_nr_running(rq_of_dl_rq(dl_rq), 1);
0980:   
0981:   	inc_dl_deadline(dl_rq, deadline);
0982:   	inc_dl_migration(dl_se, dl_rq);
0983:   }
0984:   
0985:   static inline
0986:   void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
0987:   {
0988:   	int prio = dl_task_of(dl_se)->prio;
0989:   
0990:   	WARN_ON(!dl_prio(prio));
0991:   	WARN_ON(!dl_rq->dl_nr_running);
0992:   	dl_rq->dl_nr_running--;
0993:   	sub_nr_running(rq_of_dl_rq(dl_rq), 1);
0994:   
0995:   	dec_dl_deadline(dl_rq, dl_se->deadline);
0996:   	dec_dl_migration(dl_se, dl_rq);
0997:   }
0998:   
0999:   static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
1000:   {
1001:   	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1002:   	struct rb_node **link = &dl_rq->rb_root.rb_node;
1003:   	struct rb_node *parent = NULL;
1004:   	struct sched_dl_entity *entry;
1005:   	int leftmost = 1;
1006:   
1007:   	BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));
1008:   
1009:   	while (*link) {
1010:   		parent = *link;
1011:   		entry = rb_entry(parent, struct sched_dl_entity, rb_node);
1012:   		if (dl_time_before(dl_se->deadline, entry->deadline))
1013:   			link = &parent->rb_left;
1014:   		else {
1015:   			link = &parent->rb_right;
1016:   			leftmost = 0;
1017:   		}
1018:   	}
1019:   
1020:   	if (leftmost)
1021:   		dl_rq->rb_leftmost = &dl_se->rb_node;
1022:   
1023:   	rb_link_node(&dl_se->rb_node, parent, link);
1024:   	rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root);
1025:   
1026:   	inc_dl_tasks(dl_se, dl_rq);
1027:   }
1028:   
1029:   static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
1030:   {
1031:   	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
1032:   
1033:   	if (RB_EMPTY_NODE(&dl_se->rb_node))
1034:   		return;
1035:   
1036:   	if (dl_rq->rb_leftmost == &dl_se->rb_node) {
1037:   		struct rb_node *next_node;
1038:   
1039:   		next_node = rb_next(&dl_se->rb_node);
1040:   		dl_rq->rb_leftmost = next_node;
1041:   	}
1042:   
1043:   	rb_erase(&dl_se->rb_node, &dl_rq->rb_root);
1044:   	RB_CLEAR_NODE(&dl_se->rb_node);
1045:   
1046:   	dec_dl_tasks(dl_se, dl_rq);
1047:   }
1048:   
1049:   static void
1050:   enqueue_dl_entity(struct sched_dl_entity *dl_se,
1051:   		  struct sched_dl_entity *pi_se, int flags)
1052:   {
1053:   	BUG_ON(on_dl_rq(dl_se));
1054:   
1055:   	/*
1056:   	 * If this is a wakeup or a new instance, the scheduling
1057:   	 * parameters of the task might need updating. Otherwise,
1058:   	 * we want a replenishment of its runtime.
1059:   	 */
1060:   	if (dl_se->dl_new || flags & ENQUEUE_WAKEUP)
1061:   		update_dl_entity(dl_se, pi_se);
1062:   	else if (flags & ENQUEUE_REPLENISH)
1063:   		replenish_dl_entity(dl_se, pi_se);
1064:   
1065:   	__enqueue_dl_entity(dl_se);
1066:   }
1067:   
1068:   static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
1069:   {
1070:   	__dequeue_dl_entity(dl_se);
1071:   }
1072:   
1073:   static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1074:   {
1075:   	struct task_struct *pi_task = rt_mutex_get_top_task(p);
1076:   	struct sched_dl_entity *pi_se = &p->dl;
1077:   
1078:   	/*
1079:   	 * Use the scheduling parameters of the top pi-waiter
1080:   	 * task if we have one and its (absolute) deadline is
1081:   	 * smaller than our one... OTW we keep our runtime and
1082:   	 * deadline.
1083:   	 */
1084:   	if (pi_task && p->dl.dl_boosted && dl_prio(pi_task->normal_prio)) {
1085:   		pi_se = &pi_task->dl;
1086:   	} else if (!dl_prio(p->normal_prio)) {
1087:   		/*
1088:   		 * Special case in which we have a !SCHED_DEADLINE task
1089:   		 * that is going to be deboosted, but exceedes its
1090:   		 * runtime while doing so. No point in replenishing
1091:   		 * it, as it's going to return back to its original
1092:   		 * scheduling class after this.
1093:   		 */
1094:   		BUG_ON(!p->dl.dl_boosted || flags != ENQUEUE_REPLENISH);
1095:   		return;
1096:   	}
1097:   
1098:   	/*
1099:   	 * Check if a constrained deadline task was activated
1100:   	 * after the deadline but before the next period.
1101:   	 * If that is the case, the task will be throttled and
1102:   	 * the replenishment timer will be set to the next period.
1103:   	 */
1104:   	if (!p->dl.dl_throttled && !dl_is_implicit(&p->dl))
1105:   		dl_check_constrained_dl(&p->dl);
1106:   
1107:   	/*
1108:   	 * If p is throttled, we do nothing. In fact, if it exhausted
1109:   	 * its budget it needs a replenishment and, since it now is on
1110:   	 * its rq, the bandwidth timer callback (which clearly has not
1111:   	 * run yet) will take care of this.
1112:   	 */
1113:   	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
1114:   		return;
1115:   
1116:   	enqueue_dl_entity(&p->dl, pi_se, flags);
1117:   
1118:   	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
1119:   		enqueue_pushable_dl_task(rq, p);
1120:   }
1121:   
1122:   static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1123:   {
1124:   	dequeue_dl_entity(&p->dl);
1125:   	dequeue_pushable_dl_task(rq, p);
1126:   }
1127:   
1128:   static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
1129:   {
1130:   	update_curr_dl(rq);
1131:   	__dequeue_task_dl(rq, p, flags);
1132:   }
1133:   
1134:   /*
1135:    * Yield task semantic for -deadline tasks is:
1136:    *
1137:    *   get off from the CPU until our next instance, with
1138:    *   a new runtime. This is of little use now, since we
1139:    *   don't have a bandwidth reclaiming mechanism. Anyway,
1140:    *   bandwidth reclaiming is planned for the future, and
1141:    *   yield_task_dl will indicate that some spare budget
1142:    *   is available for other task instances to use it.
1143:    */
1144:   static void yield_task_dl(struct rq *rq)
1145:   {
1146:   	struct task_struct *p = rq->curr;
1147:   
1148:   	/*
1149:   	 * We make the task go to sleep until its current deadline by
1150:   	 * forcing its runtime to zero. This way, update_curr_dl() stops
1151:   	 * it and the bandwidth timer will wake it up and will give it
1152:   	 * new scheduling parameters (thanks to dl_yielded=1).
1153:   	 */
1154:   	if (p->dl.runtime > 0) {
1155:   		rq->curr->dl.dl_yielded = 1;
1156:   		p->dl.runtime = 0;
1157:   	}
1158:   	update_rq_clock(rq);
1159:   	update_curr_dl(rq);
1160:   	/*
1161:   	 * Tell update_rq_clock() that we've just updated,
1162:   	 * so we don't do microscopic update in schedule()
1163:   	 * and double the fastpath cost.
1164:   	 */
1165:   	rq_clock_skip_update(rq, true);
1166:   }
1167:   
1168:   #ifdef CONFIG_SMP
1169:   
1170:   static int find_later_rq(struct task_struct *task);
1171:   
1172:   static int
1173:   select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
1174:   {
1175:   	struct task_struct *curr;
1176:   	struct rq *rq;
1177:   
1178:   	if (sd_flag != SD_BALANCE_WAKE)
1179:   		goto out;
1180:   
1181:   	rq = cpu_rq(cpu);
1182:   
1183:   	rcu_read_lock();
1184:   	curr = READ_ONCE(rq->curr); /* unlocked access */
1185:   
1186:   	/*
1187:   	 * If we are dealing with a -deadline task, we must
1188:   	 * decide where to wake it up.
1189:   	 * If it has a later deadline and the current task
1190:   	 * on this rq can't move (provided the waking task
1191:   	 * can!) we prefer to send it somewhere else. On the
1192:   	 * other hand, if it has a shorter deadline, we
1193:   	 * try to make it stay here, it might be important.
1194:   	 */
1195:   	if (unlikely(dl_task(curr)) &&
1196:   	    (curr->nr_cpus_allowed < 2 ||
1197:   	     !dl_entity_preempt(&p->dl, &curr->dl)) &&
1198:   	    (p->nr_cpus_allowed > 1)) {
1199:   		int target = find_later_rq(p);
1200:   
1201:   		if (target != -1 &&
1202:   				(dl_time_before(p->dl.deadline,
1203:   					cpu_rq(target)->dl.earliest_dl.curr) ||
1204:   				(cpu_rq(target)->dl.dl_nr_running == 0)))
1205:   			cpu = target;
1206:   	}
1207:   	rcu_read_unlock();
1208:   
1209:   out:
1210:   	return cpu;
1211:   }
1212:   
1213:   static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
1214:   {
1215:   	/*
1216:   	 * Current can't be migrated, useless to reschedule,
1217:   	 * let's hope p can move out.
1218:   	 */
1219:   	if (rq->curr->nr_cpus_allowed == 1 ||
1220:   	    cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1)
1221:   		return;
1222:   
1223:   	/*
1224:   	 * p is migratable, so let's not schedule it and
1225:   	 * see if it is pushed or pulled somewhere else.
1226:   	 */
1227:   	if (p->nr_cpus_allowed != 1 &&
1228:   	    cpudl_find(&rq->rd->cpudl, p, NULL) != -1)
1229:   		return;
1230:   
1231:   	resched_curr(rq);
1232:   }
1233:   
1234:   #endif /* CONFIG_SMP */
1235:   
1236:   /*
1237:    * Only called when both the current and waking task are -deadline
1238:    * tasks.
1239:    */
1240:   static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
1241:   				  int flags)
1242:   {
1243:   	if (dl_entity_preempt(&p->dl, &rq->curr->dl)) {
1244:   		resched_curr(rq);
1245:   		return;
1246:   	}
1247:   
1248:   #ifdef CONFIG_SMP
1249:   	/*
1250:   	 * In the unlikely case current and p have the same deadline
1251:   	 * let us try to decide what's the best thing to do...
1252:   	 */
1253:   	if ((p->dl.deadline == rq->curr->dl.deadline) &&
1254:   	    !test_tsk_need_resched(rq->curr))
1255:   		check_preempt_equal_dl(rq, p);
1256:   #endif /* CONFIG_SMP */
1257:   }
1258:   
1259:   #ifdef CONFIG_SCHED_HRTICK
1260:   static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1261:   {
1262:   	hrtick_start(rq, p->dl.runtime);
1263:   }
1264:   #else /* !CONFIG_SCHED_HRTICK */
1265:   static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
1266:   {
1267:   }
1268:   #endif
1269:   
1270:   static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
1271:   						   struct dl_rq *dl_rq)
1272:   {
1273:   	struct rb_node *left = dl_rq->rb_leftmost;
1274:   
1275:   	if (!left)
1276:   		return NULL;
1277:   
1278:   	return rb_entry(left, struct sched_dl_entity, rb_node);
1279:   }
1280:   
1281:   struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev)
1282:   {
1283:   	struct sched_dl_entity *dl_se;
1284:   	struct task_struct *p;
1285:   	struct dl_rq *dl_rq;
1286:   
1287:   	dl_rq = &rq->dl;
1288:   
1289:   	if (need_pull_dl_task(rq, prev)) {
1290:   		/*
1291:   		 * This is OK, because current is on_cpu, which avoids it being
1292:   		 * picked for load-balance and preemption/IRQs are still
1293:   		 * disabled avoiding further scheduler activity on it and we're
1294:   		 * being very careful to re-start the picking loop.
1295:   		 */
1296:   		lockdep_unpin_lock(&rq->lock);
1297:   		pull_dl_task(rq);
1298:   		lockdep_pin_lock(&rq->lock);
1299:   		/*
1300:   		 * pull_rt_task() can drop (and re-acquire) rq->lock; this
1301:   		 * means a stop task can slip in, in which case we need to
1302:   		 * re-start task selection.
1303:   		 */
1304:   		if (rq->stop && task_on_rq_queued(rq->stop))
1305:   			return RETRY_TASK;
1306:   	}
1307:   
1308:   	/*
1309:   	 * When prev is DL, we may throttle it in put_prev_task().
1310:   	 * So, we update time before we check for dl_nr_running.
1311:   	 */
1312:   	if (prev->sched_class == &dl_sched_class)
1313:   		update_curr_dl(rq);
1314:   
1315:   	if (unlikely(!dl_rq->dl_nr_running))
1316:   		return NULL;
1317:   
1318:   	put_prev_task(rq, prev);
1319:   
1320:   	dl_se = pick_next_dl_entity(rq, dl_rq);
1321:   	BUG_ON(!dl_se);
1322:   
1323:   	p = dl_task_of(dl_se);
1324:   	p->se.exec_start = rq_clock_task(rq);
1325:   
1326:   	/* Running task will never be pushed. */
1327:          dequeue_pushable_dl_task(rq, p);
1328:   
1329:   	if (hrtick_enabled(rq))
1330:   		start_hrtick_dl(rq, p);
1331:   
1332:   	queue_push_tasks(rq);
1333:   
1334:   	return p;
1335:   }
1336:   
1337:   static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
1338:   {
1339:   	update_curr_dl(rq);
1340:   
1341:   	if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1)
1342:   		enqueue_pushable_dl_task(rq, p);
1343:   }
1344:   
1345:   static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
1346:   {
1347:   	update_curr_dl(rq);
1348:   
1349:   	/*
1350:   	 * Even when we have runtime, update_curr_dl() might have resulted in us
1351:   	 * not being the leftmost task anymore. In that case NEED_RESCHED will
1352:   	 * be set and schedule() will start a new hrtick for the next task.
1353:   	 */
1354:   	if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
1355:   	    is_leftmost(p, &rq->dl))
1356:   		start_hrtick_dl(rq, p);
1357:   }
1358:   
1359:   static void task_fork_dl(struct task_struct *p)
1360:   {
1361:   	/*
1362:   	 * SCHED_DEADLINE tasks cannot fork and this is achieved through
1363:   	 * sched_fork()
1364:   	 */
1365:   }
1366:   
1367:   static void task_dead_dl(struct task_struct *p)
1368:   {
1369:   	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
1370:   
1371:   	/*
1372:   	 * Since we are TASK_DEAD we won't slip out of the domain!
1373:   	 */
1374:   	raw_spin_lock_irq(&dl_b->lock);
1375:   	/* XXX we should retain the bw until 0-lag */
1376:   	dl_b->total_bw -= p->dl.dl_bw;
1377:   	raw_spin_unlock_irq(&dl_b->lock);
1378:   }
1379:   
1380:   static void set_curr_task_dl(struct rq *rq)
1381:   {
1382:   	struct task_struct *p = rq->curr;
1383:   
1384:   	p->se.exec_start = rq_clock_task(rq);
1385:   
1386:   	/* You can't push away the running task */
1387:   	dequeue_pushable_dl_task(rq, p);
1388:   }
1389:   
1390:   #ifdef CONFIG_SMP
1391:   
1392:   /* Only try algorithms three times */
1393:   #define DL_MAX_TRIES 3
1394:   
1395:   static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
1396:   {
1397:   	if (!task_running(rq, p) &&
1398:   	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1399:   		return 1;
1400:   	return 0;
1401:   }
1402:   
1403:   /* Returns the second earliest -deadline task, NULL otherwise */
1404:   static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu)
1405:   {
1406:   	struct rb_node *next_node = rq->dl.rb_leftmost;
1407:   	struct sched_dl_entity *dl_se;
1408:   	struct task_struct *p = NULL;
1409:   
1410:   next_node:
1411:   	next_node = rb_next(next_node);
1412:   	if (next_node) {
1413:   		dl_se = rb_entry(next_node, struct sched_dl_entity, rb_node);
1414:   		p = dl_task_of(dl_se);
1415:   
1416:   		if (pick_dl_task(rq, p, cpu))
1417:   			return p;
1418:   
1419:   		goto next_node;
1420:   	}
1421:   
1422:   	return NULL;
1423:   }
1424:   
1425:   /*
1426:    * Return the earliest pushable rq's task, which is suitable to be executed
1427:    * on the CPU, NULL otherwise:
1428:    */
1429:   static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
1430:   {
1431:   	struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
1432:   	struct task_struct *p = NULL;
1433:   
1434:   	if (!has_pushable_dl_tasks(rq))
1435:   		return NULL;
1436:   
1437:   next_node:
1438:   	if (next_node) {
1439:   		p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);
1440:   
1441:   		if (pick_dl_task(rq, p, cpu))
1442:   			return p;
1443:   
1444:   		next_node = rb_next(next_node);
1445:   		goto next_node;
1446:   	}
1447:   
1448:   	return NULL;
1449:   }
1450:   
1451:   static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);
1452:   
1453:   static int find_later_rq(struct task_struct *task)
1454:   {
1455:   	struct sched_domain *sd;
1456:   	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
1457:   	int this_cpu = smp_processor_id();
1458:   	int best_cpu, cpu = task_cpu(task);
1459:   
1460:   	/* Make sure the mask is initialized first */
1461:   	if (unlikely(!later_mask))
1462:   		return -1;
1463:   
1464:   	if (task->nr_cpus_allowed == 1)
1465:   		return -1;
1466:   
1467:   	/*
1468:   	 * We have to consider system topology and task affinity
1469:   	 * first, then we can look for a suitable cpu.
1470:   	 */
1471:   	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
1472:   			task, later_mask);
1473:   	if (best_cpu == -1)
1474:   		return -1;
1475:   
1476:   	/*
1477:   	 * If we are here, some target has been found,
1478:   	 * the most suitable of which is cached in best_cpu.
1479:   	 * This is, among the runqueues where the current tasks
1480:   	 * have later deadlines than the task's one, the rq
1481:   	 * with the latest possible one.
1482:   	 *
1483:   	 * Now we check how well this matches with task's
1484:   	 * affinity and system topology.
1485:   	 *
1486:   	 * The last cpu where the task run is our first
1487:   	 * guess, since it is most likely cache-hot there.
1488:   	 */
1489:   	if (cpumask_test_cpu(cpu, later_mask))
1490:   		return cpu;
1491:   	/*
1492:   	 * Check if this_cpu is to be skipped (i.e., it is
1493:   	 * not in the mask) or not.
1494:   	 */
1495:   	if (!cpumask_test_cpu(this_cpu, later_mask))
1496:   		this_cpu = -1;
1497:   
1498:   	rcu_read_lock();
1499:   	for_each_domain(cpu, sd) {
1500:   		if (sd->flags & SD_WAKE_AFFINE) {
1501:   
1502:   			/*
1503:   			 * If possible, preempting this_cpu is
1504:   			 * cheaper than migrating.
1505:   			 */
1506:   			if (this_cpu != -1 &&
1507:   			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
1508:   				rcu_read_unlock();
1509:   				return this_cpu;
1510:   			}
1511:   
1512:   			/*
1513:   			 * Last chance: if best_cpu is valid and is
1514:   			 * in the mask, that becomes our choice.
1515:   			 */
1516:   			if (best_cpu < nr_cpu_ids &&
1517:   			    cpumask_test_cpu(best_cpu, sched_domain_span(sd))) {
1518:   				rcu_read_unlock();
1519:   				return best_cpu;
1520:   			}
1521:   		}
1522:   	}
1523:   	rcu_read_unlock();
1524:   
1525:   	/*
1526:   	 * At this point, all our guesses failed, we just return
1527:   	 * 'something', and let the caller sort the things out.
1528:   	 */
1529:   	if (this_cpu != -1)
1530:   		return this_cpu;
1531:   
1532:   	cpu = cpumask_any(later_mask);
1533:   	if (cpu < nr_cpu_ids)
1534:   		return cpu;
1535:   
1536:   	return -1;
1537:   }
1538:   
1539:   /* Locks the rq it finds */
1540:   static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
1541:   {
1542:   	struct rq *later_rq = NULL;
1543:   	int tries;
1544:   	int cpu;
1545:   
1546:   	for (tries = 0; tries < DL_MAX_TRIES; tries++) {
1547:   		cpu = find_later_rq(task);
1548:   
1549:   		if ((cpu == -1) || (cpu == rq->cpu))
1550:   			break;
1551:   
1552:   		later_rq = cpu_rq(cpu);
1553:   
1554:   		if (later_rq->dl.dl_nr_running &&
1555:   		    !dl_time_before(task->dl.deadline,
1556:   					later_rq->dl.earliest_dl.curr)) {
1557:   			/*
1558:   			 * Target rq has tasks of equal or earlier deadline,
1559:   			 * retrying does not release any lock and is unlikely
1560:   			 * to yield a different result.
1561:   			 */
1562:   			later_rq = NULL;
1563:   			break;
1564:   		}
1565:   
1566:   		/* Retry if something changed. */
1567:   		if (double_lock_balance(rq, later_rq)) {
1568:   			if (unlikely(task_rq(task) != rq ||
1569:   				     !cpumask_test_cpu(later_rq->cpu,
1570:   				                       &task->cpus_allowed) ||
1571:   				     task_running(rq, task) ||
1572:   				     !task_on_rq_queued(task))) {
1573:   				double_unlock_balance(rq, later_rq);
1574:   				later_rq = NULL;
1575:   				break;
1576:   			}
1577:   		}
1578:   
1579:   		/*
1580:   		 * If the rq we found has no -deadline task, or
1581:   		 * its earliest one has a later deadline than our
1582:   		 * task, the rq is a good one.
1583:   		 */
1584:   		if (!later_rq->dl.dl_nr_running ||
1585:   		    dl_time_before(task->dl.deadline,
1586:   				   later_rq->dl.earliest_dl.curr))
1587:   			break;
1588:   
1589:   		/* Otherwise we try again. */
1590:   		double_unlock_balance(rq, later_rq);
1591:   		later_rq = NULL;
1592:   	}
1593:   
1594:   	return later_rq;
1595:   }
1596:   
1597:   static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
1598:   {
1599:   	struct task_struct *p;
1600:   
1601:   	if (!has_pushable_dl_tasks(rq))
1602:   		return NULL;
1603:   
1604:   	p = rb_entry(rq->dl.pushable_dl_tasks_leftmost,
1605:   		     struct task_struct, pushable_dl_tasks);
1606:   
1607:   	BUG_ON(rq->cpu != task_cpu(p));
1608:   	BUG_ON(task_current(rq, p));
1609:   	BUG_ON(p->nr_cpus_allowed <= 1);
1610:   
1611:   	BUG_ON(!task_on_rq_queued(p));
1612:   	BUG_ON(!dl_task(p));
1613:   
1614:   	return p;
1615:   }
1616:   
1617:   /*
1618:    * See if the non running -deadline tasks on this rq
1619:    * can be sent to some other CPU where they can preempt
1620:    * and start executing.
1621:    */
1622:   static int push_dl_task(struct rq *rq)
1623:   {
1624:   	struct task_struct *next_task;
1625:   	struct rq *later_rq;
1626:   	int ret = 0;
1627:   
1628:   	if (!rq->dl.overloaded)
1629:   		return 0;
1630:   
1631:   	next_task = pick_next_pushable_dl_task(rq);
1632:   	if (!next_task)
1633:   		return 0;
1634:   
1635:   retry:
1636:   	if (unlikely(next_task == rq->curr)) {
1637:   		WARN_ON(1);
1638:   		return 0;
1639:   	}
1640:   
1641:   	/*
1642:   	 * If next_task preempts rq->curr, and rq->curr
1643:   	 * can move away, it makes sense to just reschedule
1644:   	 * without going further in pushing next_task.
1645:   	 */
1646:   	if (dl_task(rq->curr) &&
1647:   	    dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&
1648:   	    rq->curr->nr_cpus_allowed > 1) {
1649:   		resched_curr(rq);
1650:   		return 0;
1651:   	}
1652:   
1653:   	/* We might release rq lock */
1654:   	get_task_struct(next_task);
1655:   
1656:   	/* Will lock the rq it'll find */
1657:   	later_rq = find_lock_later_rq(next_task, rq);
1658:   	if (!later_rq) {
1659:   		struct task_struct *task;
1660:   
1661:   		/*
1662:   		 * We must check all this again, since
1663:   		 * find_lock_later_rq releases rq->lock and it is
1664:   		 * then possible that next_task has migrated.
1665:   		 */
1666:   		task = pick_next_pushable_dl_task(rq);
1667:   		if (task_cpu(next_task) == rq->cpu && task == next_task) {
1668:   			/*
1669:   			 * The task is still there. We don't try
1670:   			 * again, some other cpu will pull it when ready.
1671:   			 */
1672:   			goto out;
1673:   		}
1674:   
1675:   		if (!task)
1676:   			/* No more tasks */
1677:   			goto out;
1678:   
1679:   		put_task_struct(next_task);
1680:   		next_task = task;
1681:   		goto retry;
1682:   	}
1683:   
1684:   	deactivate_task(rq, next_task, 0);
1685:   	set_task_cpu(next_task, later_rq->cpu);
1686:   	activate_task(later_rq, next_task, 0);
1687:   	ret = 1;
1688:   
1689:   	resched_curr(later_rq);
1690:   
1691:   	double_unlock_balance(rq, later_rq);
1692:   
1693:   out:
1694:   	put_task_struct(next_task);
1695:   
1696:   	return ret;
1697:   }
1698:   
1699:   static void push_dl_tasks(struct rq *rq)
1700:   {
1701:   	/* push_dl_task() will return true if it moved a -deadline task */
1702:   	while (push_dl_task(rq))
1703:   		;
1704:   }
1705:   
1706:   static void pull_dl_task(struct rq *this_rq)
1707:   {
1708:   	int this_cpu = this_rq->cpu, cpu;
1709:   	struct task_struct *p;
1710:   	bool resched = false;
1711:   	struct rq *src_rq;
1712:   	u64 dmin = LONG_MAX;
1713:   
1714:   	if (likely(!dl_overloaded(this_rq)))
1715:   		return;
1716:   
1717:   	/*
1718:   	 * Match the barrier from dl_set_overloaded; this guarantees that if we
1719:   	 * see overloaded we must also see the dlo_mask bit.
1720:   	 */
1721:   	smp_rmb();
1722:   
1723:   	for_each_cpu(cpu, this_rq->rd->dlo_mask) {
1724:   		if (this_cpu == cpu)
1725:   			continue;
1726:   
1727:   		src_rq = cpu_rq(cpu);
1728:   
1729:   		/*
1730:   		 * It looks racy, abd it is! However, as in sched_rt.c,
1731:   		 * we are fine with this.
1732:   		 */
1733:   		if (this_rq->dl.dl_nr_running &&
1734:   		    dl_time_before(this_rq->dl.earliest_dl.curr,
1735:   				   src_rq->dl.earliest_dl.next))
1736:   			continue;
1737:   
1738:   		/* Might drop this_rq->lock */
1739:   		double_lock_balance(this_rq, src_rq);
1740:   
1741:   		/*
1742:   		 * If there are no more pullable tasks on the
1743:   		 * rq, we're done with it.
1744:   		 */
1745:   		if (src_rq->dl.dl_nr_running <= 1)
1746:   			goto skip;
1747:   
1748:   		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
1749:   
1750:   		/*
1751:   		 * We found a task to be pulled if:
1752:   		 *  - it preempts our current (if there's one),
1753:   		 *  - it will preempt the last one we pulled (if any).
1754:   		 */
1755:   		if (p && dl_time_before(p->dl.deadline, dmin) &&
1756:   		    (!this_rq->dl.dl_nr_running ||
1757:   		     dl_time_before(p->dl.deadline,
1758:   				    this_rq->dl.earliest_dl.curr))) {
1759:   			WARN_ON(p == src_rq->curr);
1760:   			WARN_ON(!task_on_rq_queued(p));
1761:   
1762:   			/*
1763:   			 * Then we pull iff p has actually an earlier
1764:   			 * deadline than the current task of its runqueue.
1765:   			 */
1766:   			if (dl_time_before(p->dl.deadline,
1767:   					   src_rq->curr->dl.deadline))
1768:   				goto skip;
1769:   
1770:   			resched = true;
1771:   
1772:   			deactivate_task(src_rq, p, 0);
1773:   			set_task_cpu(p, this_cpu);
1774:   			activate_task(this_rq, p, 0);
1775:   			dmin = p->dl.deadline;
1776:   
1777:   			/* Is there any other task even earlier? */
1778:   		}
1779:   skip:
1780:   		double_unlock_balance(this_rq, src_rq);
1781:   	}
1782:   
1783:   	if (resched)
1784:   		resched_curr(this_rq);
1785:   }
1786:   
1787:   /*
1788:    * Since the task is not running and a reschedule is not going to happen
1789:    * anytime soon on its runqueue, we try pushing it away now.
1790:    */
1791:   static void task_woken_dl(struct rq *rq, struct task_struct *p)
1792:   {
1793:   	if (!task_running(rq, p) &&
1794:   	    !test_tsk_need_resched(rq->curr) &&
1795:   	    p->nr_cpus_allowed > 1 &&
1796:   	    dl_task(rq->curr) &&
1797:   	    (rq->curr->nr_cpus_allowed < 2 ||
1798:   	     !dl_entity_preempt(&p->dl, &rq->curr->dl))) {
1799:   		push_dl_tasks(rq);
1800:   	}
1801:   }
1802:   
1803:   static void set_cpus_allowed_dl(struct task_struct *p,
1804:   				const struct cpumask *new_mask)
1805:   {
1806:   	struct root_domain *src_rd;
1807:   	struct rq *rq;
1808:   
1809:   	BUG_ON(!dl_task(p));
1810:   
1811:   	rq = task_rq(p);
1812:   	src_rd = rq->rd;
1813:   	/*
1814:   	 * Migrating a SCHED_DEADLINE task between exclusive
1815:   	 * cpusets (different root_domains) entails a bandwidth
1816:   	 * update. We already made space for us in the destination
1817:   	 * domain (see cpuset_can_attach()).
1818:   	 */
1819:   	if (!cpumask_intersects(src_rd->span, new_mask)) {
1820:   		struct dl_bw *src_dl_b;
1821:   
1822:   		src_dl_b = dl_bw_of(cpu_of(rq));
1823:   		/*
1824:   		 * We now free resources of the root_domain we are migrating
1825:   		 * off. In the worst case, sched_setattr() may temporary fail
1826:   		 * until we complete the update.
1827:   		 */
1828:   		raw_spin_lock(&src_dl_b->lock);
1829:   		__dl_clear(src_dl_b, p->dl.dl_bw);
1830:   		raw_spin_unlock(&src_dl_b->lock);
1831:   	}
1832:   
1833:   	set_cpus_allowed_common(p, new_mask);
1834:   }
1835:   
1836:   /* Assumes rq->lock is held */
1837:   static void rq_online_dl(struct rq *rq)
1838:   {
1839:   	if (rq->dl.overloaded)
1840:   		dl_set_overload(rq);
1841:   
1842:   	cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
1843:   	if (rq->dl.dl_nr_running > 0)
1844:   		cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr, 1);
1845:   }
1846:   
1847:   /* Assumes rq->lock is held */
1848:   static void rq_offline_dl(struct rq *rq)
1849:   {
1850:   	if (rq->dl.overloaded)
1851:   		dl_clear_overload(rq);
1852:   
1853:   	cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0);
1854:   	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
1855:   }
1856:   
1857:   void __init init_sched_dl_class(void)
1858:   {
1859:   	unsigned int i;
1860:   
1861:   	for_each_possible_cpu(i)
1862:   		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
1863:   					GFP_KERNEL, cpu_to_node(i));
1864:   }
1865:   
1866:   #endif /* CONFIG_SMP */
1867:   
1868:   static void switched_from_dl(struct rq *rq, struct task_struct *p)
1869:   {
1870:   	/*
1871:   	 * Start the deadline timer; if we switch back to dl before this we'll
1872:   	 * continue consuming our current CBS slice. If we stay outside of
1873:   	 * SCHED_DEADLINE until the deadline passes, the timer will reset the
1874:   	 * task.
1875:   	 */
1876:   	if (!start_dl_timer(p))
1877:   		__dl_clear_params(p);
1878:   
1879:   	/*
1880:   	 * Since this might be the only -deadline task on the rq,
1881:   	 * this is the right place to try to pull some other one
1882:   	 * from an overloaded cpu, if any.
1883:   	 */
1884:   	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
1885:   		return;
1886:   
1887:   	queue_pull_task(rq);
1888:   }
1889:   
1890:   /*
1891:    * When switching to -deadline, we may overload the rq, then
1892:    * we try to push someone off, if possible.
1893:    */
1894:   static void switched_to_dl(struct rq *rq, struct task_struct *p)
1895:   {
1896:   	if (task_on_rq_queued(p) && rq->curr != p) {
1897:   #ifdef CONFIG_SMP
1898:   		if (p->nr_cpus_allowed > 1 && rq->dl.overloaded)
1899:   			queue_push_tasks(rq);
1900:   #endif
1901:   		if (dl_task(rq->curr))
1902:   			check_preempt_curr_dl(rq, p, 0);
1903:   		else
1904:   			resched_curr(rq);
1905:   	}
1906:   }
1907:   
1908:   /*
1909:    * If the scheduling parameters of a -deadline task changed,
1910:    * a push or pull operation might be needed.
1911:    */
1912:   static void prio_changed_dl(struct rq *rq, struct task_struct *p,
1913:   			    int oldprio)
1914:   {
1915:   	if (task_on_rq_queued(p) || rq->curr == p) {
1916:   #ifdef CONFIG_SMP
1917:   		/*
1918:   		 * This might be too much, but unfortunately
1919:   		 * we don't have the old deadline value, and
1920:   		 * we can't argue if the task is increasing
1921:   		 * or lowering its prio, so...
1922:   		 */
1923:   		if (!rq->dl.overloaded)
1924:   			queue_pull_task(rq);
1925:   
1926:   		/*
1927:   		 * If we now have a earlier deadline task than p,
1928:   		 * then reschedule, provided p is still on this
1929:   		 * runqueue.
1930:   		 */
1931:   		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))
1932:   			resched_curr(rq);
1933:   #else
1934:   		/*
1935:   		 * Again, we don't know if p has a earlier
1936:   		 * or later deadline, so let's blindly set a
1937:   		 * (maybe not needed) rescheduling point.
1938:   		 */
1939:   		resched_curr(rq);
1940:   #endif /* CONFIG_SMP */
1941:   	} else
1942:   		switched_to_dl(rq, p);
1943:   }
1944:   
1945:   const struct sched_class dl_sched_class = {
1946:   	.next			= &rt_sched_class,
1947:   	.enqueue_task		= enqueue_task_dl,
1948:   	.dequeue_task		= dequeue_task_dl,
1949:   	.yield_task		= yield_task_dl,
1950:   
1951:   	.check_preempt_curr	= check_preempt_curr_dl,
1952:   
1953:   	.pick_next_task		= pick_next_task_dl,
1954:   	.put_prev_task		= put_prev_task_dl,
1955:   
1956:   #ifdef CONFIG_SMP
1957:   	.select_task_rq		= select_task_rq_dl,
1958:   	.set_cpus_allowed       = set_cpus_allowed_dl,
1959:   	.rq_online              = rq_online_dl,
1960:   	.rq_offline             = rq_offline_dl,
1961:   	.task_woken		= task_woken_dl,
1962:   #endif
1963:   
1964:   	.set_curr_task		= set_curr_task_dl,
1965:   	.task_tick		= task_tick_dl,
1966:   	.task_fork              = task_fork_dl,
1967:   	.task_dead		= task_dead_dl,
1968:   
1969:   	.prio_changed           = prio_changed_dl,
1970:   	.switched_from		= switched_from_dl,
1971:   	.switched_to		= switched_to_dl,
1972:   
1973:   	.update_curr		= update_curr_dl,
1974:   };
1975:   
1976:   #ifdef CONFIG_SCHED_DEBUG
1977:   extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
1978:   
1979:   void print_dl_stats(struct seq_file *m, int cpu)
1980:   {
1981:   	print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
1982:   }
1983:   #endif /* CONFIG_SCHED_DEBUG */