deadline.c 46.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12
/*
 * Deadline Scheduling Class (SCHED_DEADLINE)
 *
 * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
 *
 * Tasks that periodically executes their instances for less than their
 * runtime won't miss any of their deadlines.
 * Tasks that are not periodic or sporadic or that tries to execute more
 * than their reserved bandwidth will be slowed down (and may potentially
 * miss some of their deadlines), and won't affect any other task.
 *
 * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>,
13
 *                    Juri Lelli <juri.lelli@gmail.com>,
14 15 16 17 18
 *                    Michael Trimarchi <michael@amarulasolutions.com>,
 *                    Fabio Checconi <fchecconi@gmail.com>
 */
#include "sched.h"

19 20
#include <linux/slab.h>

21 22
struct dl_bandwidth def_dl_bandwidth;

23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
{
	return container_of(dl_se, struct task_struct, dl);
}

static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq)
{
	return container_of(dl_rq, struct rq, dl);
}

static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se)
{
	struct task_struct *p = dl_task_of(dl_se);
	struct rq *rq = task_rq(p);

	return &rq->dl;
}

static inline int on_dl_rq(struct sched_dl_entity *dl_se)
{
	return !RB_EMPTY_NODE(&dl_se->rb_node);
}

static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq)
{
	struct sched_dl_entity *dl_se = &p->dl;

	return dl_rq->rb_leftmost == &dl_se->rb_node;
}

53 54 55 56 57 58 59 60 61 62 63
void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
{
	raw_spin_lock_init(&dl_b->dl_runtime_lock);
	dl_b->dl_period = period;
	dl_b->dl_runtime = runtime;
}

void init_dl_bw(struct dl_bw *dl_b)
{
	raw_spin_lock_init(&dl_b->lock);
	raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock);
64
	if (global_rt_runtime() == RUNTIME_INF)
65 66
		dl_b->bw = -1;
	else
67
		dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime());
68 69 70 71
	raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock);
	dl_b->total_bw = 0;
}

72
void init_dl_rq(struct dl_rq *dl_rq)
73 74
{
	dl_rq->rb_root = RB_ROOT;
75 76 77 78 79 80 81 82

#ifdef CONFIG_SMP
	/* zero means no -deadline tasks */
	dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0;

	dl_rq->dl_nr_migratory = 0;
	dl_rq->overloaded = 0;
	dl_rq->pushable_dl_tasks_root = RB_ROOT;
83 84
#else
	init_dl_bw(&dl_rq->dl_bw);
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
#endif
}

#ifdef CONFIG_SMP

static inline int dl_overloaded(struct rq *rq)
{
	return atomic_read(&rq->rd->dlo_count);
}

static inline void dl_set_overload(struct rq *rq)
{
	if (!rq->online)
		return;

	cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask);
	/*
	 * Must be visible before the overload count is
	 * set (as in sched_rt.c).
	 *
	 * Matched by the barrier in pull_dl_task().
	 */
	smp_wmb();
	atomic_inc(&rq->rd->dlo_count);
}

static inline void dl_clear_overload(struct rq *rq)
{
	if (!rq->online)
		return;

	atomic_dec(&rq->rd->dlo_count);
	cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask);
}

static void update_dl_migration(struct dl_rq *dl_rq)
{
122
	if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) {
123 124 125 126 127 128 129 130 131 132 133 134 135 136
		if (!dl_rq->overloaded) {
			dl_set_overload(rq_of_dl_rq(dl_rq));
			dl_rq->overloaded = 1;
		}
	} else if (dl_rq->overloaded) {
		dl_clear_overload(rq_of_dl_rq(dl_rq));
		dl_rq->overloaded = 0;
	}
}

static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
	struct task_struct *p = dl_task_of(dl_se);

137
	if (tsk_nr_cpus_allowed(p) > 1)
138 139 140 141 142 143 144 145 146
		dl_rq->dl_nr_migratory++;

	update_dl_migration(dl_rq);
}

static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
	struct task_struct *p = dl_task_of(dl_se);

147
	if (tsk_nr_cpus_allowed(p) > 1)
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
		dl_rq->dl_nr_migratory--;

	update_dl_migration(dl_rq);
}

/*
 * The list of pushable -deadline task is not a plist, like in
 * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
 */
static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
	struct dl_rq *dl_rq = &rq->dl;
	struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_node;
	struct rb_node *parent = NULL;
	struct task_struct *entry;
	int leftmost = 1;

	BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));

	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct task_struct,
				 pushable_dl_tasks);
		if (dl_entity_preempt(&p->dl, &entry->dl))
			link = &parent->rb_left;
		else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

179
	if (leftmost) {
180
		dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks;
181 182
		dl_rq->earliest_dl.next = p->dl.deadline;
	}
183 184 185

	rb_link_node(&p->pushable_dl_tasks, parent, link);
	rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
186 187
}

188 189 190 191 192 193 194 195 196 197 198 199
static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
	struct dl_rq *dl_rq = &rq->dl;

	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
		return;

	if (dl_rq->pushable_dl_tasks_leftmost == &p->pushable_dl_tasks) {
		struct rb_node *next_node;

		next_node = rb_next(&p->pushable_dl_tasks);
		dl_rq->pushable_dl_tasks_leftmost = next_node;
200 201 202 203
		if (next_node) {
			dl_rq->earliest_dl.next = rb_entry(next_node,
				struct task_struct, pushable_dl_tasks)->dl.deadline;
		}
204 205 206 207 208 209 210 211 212 213 214 215 216
	}

	rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
	RB_CLEAR_NODE(&p->pushable_dl_tasks);
}

static inline int has_pushable_dl_tasks(struct rq *rq)
{
	return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root);
}

static int push_dl_task(struct rq *rq);

P
Peter Zijlstra 已提交
217 218 219 220 221
static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
{
	return dl_task(prev);
}

222 223
static DEFINE_PER_CPU(struct callback_head, dl_push_head);
static DEFINE_PER_CPU(struct callback_head, dl_pull_head);
224 225

static void push_dl_tasks(struct rq *);
226
static void pull_dl_task(struct rq *);
227 228

static inline void queue_push_tasks(struct rq *rq)
P
Peter Zijlstra 已提交
229
{
230 231 232
	if (!has_pushable_dl_tasks(rq))
		return;

233 234 235 236 237 238
	queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks);
}

static inline void queue_pull_task(struct rq *rq)
{
	queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task);
P
Peter Zijlstra 已提交
239 240
}

241 242
static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);

243
static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p)
244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276
{
	struct rq *later_rq = NULL;
	bool fallback = false;

	later_rq = find_lock_later_rq(p, rq);

	if (!later_rq) {
		int cpu;

		/*
		 * If we cannot preempt any rq, fall back to pick any
		 * online cpu.
		 */
		fallback = true;
		cpu = cpumask_any_and(cpu_active_mask, tsk_cpus_allowed(p));
		if (cpu >= nr_cpu_ids) {
			/*
			 * Fail to find any suitable cpu.
			 * The task will never come back!
			 */
			BUG_ON(dl_bandwidth_enabled());

			/*
			 * If admission control is disabled we
			 * try a little harder to let the task
			 * run.
			 */
			cpu = cpumask_any(cpu_active_mask);
		}
		later_rq = cpu_rq(cpu);
		double_lock_balance(rq, later_rq);
	}

277 278 279
	/*
	 * By now the task is replenished and enqueued; migrate it.
	 */
280 281
	deactivate_task(rq, p, 0);
	set_task_cpu(p, later_rq->cpu);
282
	activate_task(later_rq, p, 0);
283 284 285 286

	if (!fallback)
		resched_curr(later_rq);

287 288 289
	double_unlock_balance(later_rq, rq);

	return later_rq;
290 291
}

292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
#else

static inline
void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
}

static inline
void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
{
}

static inline
void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
}

static inline
void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
}

P
Peter Zijlstra 已提交
314 315 316 317 318
static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev)
{
	return false;
}

319
static inline void pull_dl_task(struct rq *rq)
P
Peter Zijlstra 已提交
320 321 322
{
}

323
static inline void queue_push_tasks(struct rq *rq)
P
Peter Zijlstra 已提交
324 325 326
{
}

327
static inline void queue_pull_task(struct rq *rq)
P
Peter Zijlstra 已提交
328 329
{
}
330 331
#endif /* CONFIG_SMP */

332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags);
static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags);
static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
				  int flags);

/*
 * We are being explicitly informed that a new instance is starting,
 * and this means that:
 *  - the absolute deadline of the entity has to be placed at
 *    current time + relative deadline;
 *  - the runtime of the entity has to be set to the maximum value.
 *
 * The capability of specifying such event is useful whenever a -deadline
 * entity wants to (try to!) synchronize its behaviour with the scheduler's
 * one, and to (try to!) reconcile itself with its own scheduling
 * parameters.
 */
349
static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
350 351 352 353
{
	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
	struct rq *rq = rq_of_dl_rq(dl_rq);

354
	WARN_ON(dl_se->dl_boosted);
355 356 357 358 359 360 361 362 363
	WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline));

	/*
	 * We are racing with the deadline timer. So, do nothing because
	 * the deadline timer handler will take care of properly recharging
	 * the runtime and postponing the deadline
	 */
	if (dl_se->dl_throttled)
		return;
364 365 366 367 368 369

	/*
	 * We use the regular wall clock time to set deadlines in the
	 * future; in fact, we must consider execution overheads (time
	 * spent on hardirq context, etc.).
	 */
370 371
	dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
	dl_se->runtime = dl_se->dl_runtime;
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
}

/*
 * Pure Earliest Deadline First (EDF) scheduling does not deal with the
 * possibility of a entity lasting more than what it declared, and thus
 * exhausting its runtime.
 *
 * Here we are interested in making runtime overrun possible, but we do
 * not want a entity which is misbehaving to affect the scheduling of all
 * other entities.
 * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS)
 * is used, in order to confine each entity within its own bandwidth.
 *
 * This function deals exactly with that, and ensures that when the runtime
 * of a entity is replenished, its deadline is also postponed. That ensures
 * the overrunning entity can't interfere with other entity in the system and
 * can't make them miss their deadlines. Reasons why this kind of overruns
 * could happen are, typically, a entity voluntarily trying to overcome its
390
 * runtime, or it just underestimated it during sched_setattr().
391
 */
392 393
static void replenish_dl_entity(struct sched_dl_entity *dl_se,
				struct sched_dl_entity *pi_se)
394 395 396 397
{
	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
	struct rq *rq = rq_of_dl_rq(dl_rq);

398 399 400 401 402 403 404 405 406 407 408
	BUG_ON(pi_se->dl_runtime <= 0);

	/*
	 * This could be the case for a !-dl task that is boosted.
	 * Just go with full inherited parameters.
	 */
	if (dl_se->dl_deadline == 0) {
		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
		dl_se->runtime = pi_se->dl_runtime;
	}

409 410 411
	if (dl_se->dl_yielded && dl_se->runtime > 0)
		dl_se->runtime = 0;

412 413 414 415 416 417 418
	/*
	 * We keep moving the deadline away until we get some
	 * available runtime for the entity. This ensures correct
	 * handling of situations where the runtime overrun is
	 * arbitrary large.
	 */
	while (dl_se->runtime <= 0) {
419 420
		dl_se->deadline += pi_se->dl_period;
		dl_se->runtime += pi_se->dl_runtime;
421 422 423 424 425 426 427 428 429 430 431 432
	}

	/*
	 * At this point, the deadline really should be "in
	 * the future" with respect to rq->clock. If it's
	 * not, we are, for some reason, lagging too much!
	 * Anyway, after having warn userspace abut that,
	 * we still try to keep the things running by
	 * resetting the deadline and the budget of the
	 * entity.
	 */
	if (dl_time_before(dl_se->deadline, rq_clock(rq))) {
433
		printk_deferred_once("sched: DL replenish lagged too much\n");
434 435
		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
		dl_se->runtime = pi_se->dl_runtime;
436
	}
437 438 439 440 441

	if (dl_se->dl_yielded)
		dl_se->dl_yielded = 0;
	if (dl_se->dl_throttled)
		dl_se->dl_throttled = 0;
442 443 444 445 446 447 448 449 450 451 452 453 454
}

/*
 * Here we check if --at time t-- an entity (which is probably being
 * [re]activated or, in general, enqueued) can use its remaining runtime
 * and its current deadline _without_ exceeding the bandwidth it is
 * assigned (function returns true if it can't). We are in fact applying
 * one of the CBS rules: when a task wakes up, if the residual runtime
 * over residual deadline fits within the allocated bandwidth, then we
 * can keep the current (absolute) deadline and residual budget without
 * disrupting the schedulability of the system. Otherwise, we should
 * refill the runtime and set the deadline a period in the future,
 * because keeping the current (absolute) deadline of the task would
455 456
 * result in breaking guarantees promised to other tasks (refer to
 * Documentation/scheduler/sched-deadline.txt for more informations).
457 458 459
 *
 * This function returns true if:
 *
460
 *   runtime / (deadline - t) > dl_runtime / dl_period ,
461 462
 *
 * IOW we can't recycle current parameters.
463 464 465 466
 *
 * Notice that the bandwidth check is done against the period. For
 * task with deadline equal to period this is the same of using
 * dl_deadline instead of dl_period in the equation above.
467
 */
468 469
static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
			       struct sched_dl_entity *pi_se, u64 t)
470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
{
	u64 left, right;

	/*
	 * left and right are the two sides of the equation above,
	 * after a bit of shuffling to use multiplications instead
	 * of divisions.
	 *
	 * Note that none of the time values involved in the two
	 * multiplications are absolute: dl_deadline and dl_runtime
	 * are the relative deadline and the maximum runtime of each
	 * instance, runtime is the runtime left for the last instance
	 * and (deadline - t), since t is rq->clock, is the time left
	 * to the (absolute) deadline. Even if overflowing the u64 type
	 * is very unlikely to occur in both cases, here we scale down
	 * as we want to avoid that risk at all. Scaling down by 10
	 * means that we reduce granularity to 1us. We are fine with it,
	 * since this is only a true/false check and, anyway, thinking
	 * of anything below microseconds resolution is actually fiction
	 * (but still we want to give the user that illusion >;).
	 */
491 492 493
	left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >> DL_SCALE);
	right = ((dl_se->deadline - t) >> DL_SCALE) *
		(pi_se->dl_runtime >> DL_SCALE);
494 495 496 497 498 499 500 501 502 503 504 505 506

	return dl_time_before(right, left);
}

/*
 * When a -deadline entity is queued back on the runqueue, its runtime and
 * deadline might need updating.
 *
 * The policy here is that we update the deadline of the entity only if:
 *  - the current deadline is in the past,
 *  - using the remaining runtime with the current deadline would make
 *    the entity exceed its bandwidth.
 */
507 508
static void update_dl_entity(struct sched_dl_entity *dl_se,
			     struct sched_dl_entity *pi_se)
509 510 511 512 513
{
	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
	struct rq *rq = rq_of_dl_rq(dl_rq);

	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
514 515 516
	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
		dl_se->runtime = pi_se->dl_runtime;
517 518 519 520 521 522 523 524 525 526 527 528 529
	}
}

/*
 * If the entity depleted all its runtime, and if we want it to sleep
 * while waiting for some new execution time to become available, we
 * set the bandwidth enforcement timer to the replenishment instant
 * and try to activate it.
 *
 * Notice that it is important for the caller to know if the timer
 * actually started or not (i.e., the replenishment instant is in
 * the future or in the past).
 */
530
static int start_dl_timer(struct task_struct *p)
531
{
532 533 534
	struct sched_dl_entity *dl_se = &p->dl;
	struct hrtimer *timer = &dl_se->dl_timer;
	struct rq *rq = task_rq(p);
535 536 537
	ktime_t now, act;
	s64 delta;

538 539
	lockdep_assert_held(&rq->lock);

540 541 542 543 544 545
	/*
	 * We want the timer to fire at the deadline, but considering
	 * that it is actually coming from rq->clock and not from
	 * hrtimer's time base reading.
	 */
	act = ns_to_ktime(dl_se->deadline);
546
	now = hrtimer_cb_get_time(timer);
547 548 549 550 551 552 553 554 555 556 557
	delta = ktime_to_ns(now) - rq_clock(rq);
	act = ktime_add_ns(act, delta);

	/*
	 * If the expiry time already passed, e.g., because the value
	 * chosen as the deadline is too small, don't even try to
	 * start the timer in the past!
	 */
	if (ktime_us_delta(act, now) < 0)
		return 0;

558 559 560 561 562 563 564 565 566 567 568 569 570
	/*
	 * !enqueued will guarantee another callback; even if one is already in
	 * progress. This ensures a balanced {get,put}_task_struct().
	 *
	 * The race against __run_timer() clearing the enqueued state is
	 * harmless because we're holding task_rq()->lock, therefore the timer
	 * expiring after we've done the check will wait on its task_rq_lock()
	 * and observe our state.
	 */
	if (!hrtimer_is_queued(timer)) {
		get_task_struct(p);
		hrtimer_start(timer, act, HRTIMER_MODE_ABS);
	}
571

572
	return 1;
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
}

/*
 * This is the bandwidth enforcement timer callback. If here, we know
 * a task is not on its dl_rq, since the fact that the timer was running
 * means the task is throttled and needs a runtime replenishment.
 *
 * However, what we actually do depends on the fact the task is active,
 * (it is on its rq) or has been removed from there by a call to
 * dequeue_task_dl(). In the former case we must issue the runtime
 * replenishment and add the task back to the dl_rq; in the latter, we just
 * do nothing but clearing dl_throttled, so that runtime and deadline
 * updating (and the queueing back to dl_rq) will be done by the
 * next call to enqueue_task_dl().
 */
static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
{
	struct sched_dl_entity *dl_se = container_of(timer,
						     struct sched_dl_entity,
						     dl_timer);
	struct task_struct *p = dl_task_of(dl_se);
594
	struct rq_flags rf;
595
	struct rq *rq;
596

597
	rq = task_rq_lock(p, &rf);
598

599
	/*
600 601 602 603 604 605 606 607 608 609 610 611 612 613
	 * The task might have changed its scheduling policy to something
	 * different than SCHED_DEADLINE (through switched_fromd_dl()).
	 */
	if (!dl_task(p)) {
		__dl_clear_params(p);
		goto unlock;
	}

	/*
	 * The task might have been boosted by someone else and might be in the
	 * boosting/deboosting path, its not throttled.
	 */
	if (dl_se->dl_boosted)
		goto unlock;
614

615
	/*
616 617
	 * Spurious timer due to start_dl_timer() race; or we already received
	 * a replenishment from rt_mutex_setprio().
618
	 */
619
	if (!dl_se->dl_throttled)
620
		goto unlock;
621 622 623

	sched_clock_tick();
	update_rq_clock(rq);
624

625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
	/*
	 * If the throttle happened during sched-out; like:
	 *
	 *   schedule()
	 *     deactivate_task()
	 *       dequeue_task_dl()
	 *         update_curr_dl()
	 *           start_dl_timer()
	 *         __dequeue_task_dl()
	 *     prev->on_rq = 0;
	 *
	 * We can be both throttled and !queued. Replenish the counter
	 * but do not enqueue -- wait for our wakeup to do that.
	 */
	if (!task_on_rq_queued(p)) {
		replenish_dl_entity(dl_se, dl_se);
		goto unlock;
	}

644 645 646 647 648
	enqueue_task_dl(rq, p, ENQUEUE_REPLENISH);
	if (dl_task(rq->curr))
		check_preempt_curr_dl(rq, p, 0);
	else
		resched_curr(rq);
649

650
#ifdef CONFIG_SMP
651
	/*
652 653 654 655 656 657 658 659 660
	 * Perform balancing operations here; after the replenishments.  We
	 * cannot drop rq->lock before this, otherwise the assertion in
	 * start_dl_timer() about not missing updates is not true.
	 *
	 * If we find that the rq the task was on is no longer available, we
	 * need to select a new rq.
	 *
	 * XXX figure out if select_task_rq_dl() deals with offline cpus.
	 */
661 662
	if (unlikely(!rq->online)) {
		lockdep_unpin_lock(&rq->lock, rf.cookie);
663
		rq = dl_task_offline_migration(rq, p);
664 665
		rf.cookie = lockdep_pin_lock(&rq->lock);
	}
666 667 668 669

	/*
	 * Queueing this task back might have overloaded rq, check if we need
	 * to kick someone away.
670
	 */
671 672 673 674 675
	if (has_pushable_dl_tasks(rq)) {
		/*
		 * Nothing relies on rq->lock after this, so its safe to drop
		 * rq->lock.
		 */
676
		lockdep_unpin_lock(&rq->lock, rf.cookie);
677
		push_dl_task(rq);
678
		lockdep_repin_lock(&rq->lock, rf.cookie);
679
	}
680
#endif
681

682
unlock:
683
	task_rq_unlock(rq, p, &rf);
684

685 686 687 688 689 690
	/*
	 * This can free the task_struct, including this hrtimer, do not touch
	 * anything related to that after this.
	 */
	put_task_struct(p);

691 692 693 694 695 696 697 698 699 700 701 702
	return HRTIMER_NORESTART;
}

void init_dl_task_timer(struct sched_dl_entity *dl_se)
{
	struct hrtimer *timer = &dl_se->dl_timer;

	hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
	timer->function = dl_task_timer;
}

static
703
int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
704
{
705
	return (dl_se->runtime <= 0);
706 707
}

708 709
extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);

710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731
/*
 * Update the current task's runtime statistics (provided it is still
 * a -deadline task and has not been removed from the dl_rq).
 */
static void update_curr_dl(struct rq *rq)
{
	struct task_struct *curr = rq->curr;
	struct sched_dl_entity *dl_se = &curr->dl;
	u64 delta_exec;

	if (!dl_task(curr) || !on_dl_rq(dl_se))
		return;

	/*
	 * Consumed budget is computed considering the time as
	 * observed by schedulable tasks (excluding time spent
	 * in hardirq context, etc.). Deadlines are instead
	 * computed using hard walltime. This seems to be the more
	 * natural solution, but the full ramifications of this
	 * approach need further study.
	 */
	delta_exec = rq_clock_task(rq) - curr->se.exec_start;
732 733 734
	if (unlikely((s64)delta_exec <= 0)) {
		if (unlikely(dl_se->dl_yielded))
			goto throttle;
735
		return;
736
	}
737

738 739 740 741
	/* kick cpufreq (see the comment in linux/cpufreq.h). */
	if (cpu_of(rq) == smp_processor_id())
		cpufreq_trigger_update(rq_clock(rq));

742 743 744 745 746 747 748 749 750
	schedstat_set(curr->se.statistics.exec_max,
		      max(curr->se.statistics.exec_max, delta_exec));

	curr->se.sum_exec_runtime += delta_exec;
	account_group_exec_runtime(curr, delta_exec);

	curr->se.exec_start = rq_clock_task(rq);
	cpuacct_charge(curr, delta_exec);

751 752
	sched_rt_avg_update(rq, delta_exec);

753 754 755 756
	dl_se->runtime -= delta_exec;

throttle:
	if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
757
		dl_se->dl_throttled = 1;
758
		__dequeue_task_dl(rq, curr, 0);
759
		if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
760 761 762
			enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);

		if (!is_leftmost(curr, &rq->dl))
763
			resched_curr(rq);
764
	}
765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782

	/*
	 * Because -- for now -- we share the rt bandwidth, we need to
	 * account our runtime there too, otherwise actual rt tasks
	 * would be able to exceed the shared quota.
	 *
	 * Account to the root rt group for now.
	 *
	 * The solution we're working towards is having the RT groups scheduled
	 * using deadline servers -- however there's a few nasties to figure
	 * out before that can happen.
	 */
	if (rt_bandwidth_enabled()) {
		struct rt_rq *rt_rq = &rq->rt;

		raw_spin_lock(&rt_rq->rt_runtime_lock);
		/*
		 * We'll let actual RT tasks worry about the overflow here, we
783 784
		 * have our own CBS to keep us inline; only account when RT
		 * bandwidth is relevant.
785
		 */
786 787
		if (sched_rt_bandwidth_account(rt_rq))
			rt_rq->rt_time += delta_exec;
788 789
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
	}
790 791
}

792 793 794 795 796 797 798 799 800
#ifdef CONFIG_SMP

static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
{
	struct rq *rq = rq_of_dl_rq(dl_rq);

	if (dl_rq->earliest_dl.curr == 0 ||
	    dl_time_before(deadline, dl_rq->earliest_dl.curr)) {
		dl_rq->earliest_dl.curr = deadline;
801
		cpudl_set(&rq->rd->cpudl, rq->cpu, deadline);
802 803 804 805 806 807 808 809 810 811 812 813 814 815
	}
}

static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
{
	struct rq *rq = rq_of_dl_rq(dl_rq);

	/*
	 * Since we may have removed our earliest (and/or next earliest)
	 * task we must recompute them.
	 */
	if (!dl_rq->dl_nr_running) {
		dl_rq->earliest_dl.curr = 0;
		dl_rq->earliest_dl.next = 0;
816
		cpudl_clear(&rq->rd->cpudl, rq->cpu);
817 818 819 820 821 822
	} else {
		struct rb_node *leftmost = dl_rq->rb_leftmost;
		struct sched_dl_entity *entry;

		entry = rb_entry(leftmost, struct sched_dl_entity, rb_node);
		dl_rq->earliest_dl.curr = entry->deadline;
823
		cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline);
824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841
	}
}

#else

static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}

#endif /* CONFIG_SMP */

static inline
void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
	int prio = dl_task_of(dl_se)->prio;
	u64 deadline = dl_se->deadline;

	WARN_ON(!dl_prio(prio));
	dl_rq->dl_nr_running++;
842
	add_nr_running(rq_of_dl_rq(dl_rq), 1);
843 844 845 846 847 848 849 850 851 852 853 854 855

	inc_dl_deadline(dl_rq, deadline);
	inc_dl_migration(dl_se, dl_rq);
}

static inline
void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
{
	int prio = dl_task_of(dl_se)->prio;

	WARN_ON(!dl_prio(prio));
	WARN_ON(!dl_rq->dl_nr_running);
	dl_rq->dl_nr_running--;
856
	sub_nr_running(rq_of_dl_rq(dl_rq), 1);
857 858 859 860 861

	dec_dl_deadline(dl_rq, dl_se->deadline);
	dec_dl_migration(dl_se, dl_rq);
}

862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888
static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
{
	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
	struct rb_node **link = &dl_rq->rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct sched_dl_entity *entry;
	int leftmost = 1;

	BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));

	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_dl_entity, rb_node);
		if (dl_time_before(dl_se->deadline, entry->deadline))
			link = &parent->rb_left;
		else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

	if (leftmost)
		dl_rq->rb_leftmost = &dl_se->rb_node;

	rb_link_node(&dl_se->rb_node, parent, link);
	rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root);

889
	inc_dl_tasks(dl_se, dl_rq);
890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908
}

static void __dequeue_dl_entity(struct sched_dl_entity *dl_se)
{
	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);

	if (RB_EMPTY_NODE(&dl_se->rb_node))
		return;

	if (dl_rq->rb_leftmost == &dl_se->rb_node) {
		struct rb_node *next_node;

		next_node = rb_next(&dl_se->rb_node);
		dl_rq->rb_leftmost = next_node;
	}

	rb_erase(&dl_se->rb_node, &dl_rq->rb_root);
	RB_CLEAR_NODE(&dl_se->rb_node);

909
	dec_dl_tasks(dl_se, dl_rq);
910 911 912
}

static void
913 914
enqueue_dl_entity(struct sched_dl_entity *dl_se,
		  struct sched_dl_entity *pi_se, int flags)
915 916 917 918 919 920 921 922
{
	BUG_ON(on_dl_rq(dl_se));

	/*
	 * If this is a wakeup or a new instance, the scheduling
	 * parameters of the task might need updating. Otherwise,
	 * we want a replenishment of its runtime.
	 */
923
	if (flags & ENQUEUE_WAKEUP)
924
		update_dl_entity(dl_se, pi_se);
925 926
	else if (flags & ENQUEUE_REPLENISH)
		replenish_dl_entity(dl_se, pi_se);
927 928 929 930 931 932 933 934 935 936 937

	__enqueue_dl_entity(dl_se);
}

static void dequeue_dl_entity(struct sched_dl_entity *dl_se)
{
	__dequeue_dl_entity(dl_se);
}

static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
{
938 939 940 941 942
	struct task_struct *pi_task = rt_mutex_get_top_task(p);
	struct sched_dl_entity *pi_se = &p->dl;

	/*
	 * Use the scheduling parameters of the top pi-waiter
943
	 * task if we have one and its (absolute) deadline is
944 945 946
	 * smaller than our one... OTW we keep our runtime and
	 * deadline.
	 */
947
	if (pi_task && p->dl.dl_boosted && dl_prio(pi_task->normal_prio)) {
948
		pi_se = &pi_task->dl;
949 950 951 952 953 954 955 956 957 958 959
	} else if (!dl_prio(p->normal_prio)) {
		/*
		 * Special case in which we have a !SCHED_DEADLINE task
		 * that is going to be deboosted, but exceedes its
		 * runtime while doing so. No point in replenishing
		 * it, as it's going to return back to its original
		 * scheduling class after this.
		 */
		BUG_ON(!p->dl.dl_boosted || flags != ENQUEUE_REPLENISH);
		return;
	}
960

961 962 963 964 965 966
	/*
	 * If p is throttled, we do nothing. In fact, if it exhausted
	 * its budget it needs a replenishment and, since it now is on
	 * its rq, the bandwidth timer callback (which clearly has not
	 * run yet) will take care of this.
	 */
967
	if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH))
968 969
		return;

970
	enqueue_dl_entity(&p->dl, pi_se, flags);
971

972
	if (!task_current(rq, p) && tsk_nr_cpus_allowed(p) > 1)
973
		enqueue_pushable_dl_task(rq, p);
974 975 976 977 978
}

static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
{
	dequeue_dl_entity(&p->dl);
979
	dequeue_pushable_dl_task(rq, p);
980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
}

static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
{
	update_curr_dl(rq);
	__dequeue_task_dl(rq, p, flags);
}

/*
 * Yield task semantic for -deadline tasks is:
 *
 *   get off from the CPU until our next instance, with
 *   a new runtime. This is of little use now, since we
 *   don't have a bandwidth reclaiming mechanism. Anyway,
 *   bandwidth reclaiming is planned for the future, and
 *   yield_task_dl will indicate that some spare budget
 *   is available for other task instances to use it.
 */
static void yield_task_dl(struct rq *rq)
{
	/*
	 * We make the task go to sleep until its current deadline by
	 * forcing its runtime to zero. This way, update_curr_dl() stops
	 * it and the bandwidth timer will wake it up and will give it
1004
	 * new scheduling parameters (thanks to dl_yielded=1).
1005
	 */
1006 1007
	rq->curr->dl.dl_yielded = 1;

1008
	update_rq_clock(rq);
1009
	update_curr_dl(rq);
1010 1011 1012 1013 1014 1015
	/*
	 * Tell update_rq_clock() that we've just updated,
	 * so we don't do microscopic update in schedule()
	 * and double the fastpath cost.
	 */
	rq_clock_skip_update(rq, true);
1016 1017
}

1018 1019 1020 1021 1022 1023 1024 1025 1026 1027
#ifdef CONFIG_SMP

static int find_later_rq(struct task_struct *task);

static int
select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
{
	struct task_struct *curr;
	struct rq *rq;

1028
	if (sd_flag != SD_BALANCE_WAKE)
1029 1030 1031 1032 1033
		goto out;

	rq = cpu_rq(cpu);

	rcu_read_lock();
1034
	curr = READ_ONCE(rq->curr); /* unlocked access */
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045

	/*
	 * If we are dealing with a -deadline task, we must
	 * decide where to wake it up.
	 * If it has a later deadline and the current task
	 * on this rq can't move (provided the waking task
	 * can!) we prefer to send it somewhere else. On the
	 * other hand, if it has a shorter deadline, we
	 * try to make it stay here, it might be important.
	 */
	if (unlikely(dl_task(curr)) &&
1046
	    (tsk_nr_cpus_allowed(curr) < 2 ||
1047
	     !dl_entity_preempt(&p->dl, &curr->dl)) &&
1048
	    (tsk_nr_cpus_allowed(p) > 1)) {
1049 1050
		int target = find_later_rq(p);

1051
		if (target != -1 &&
1052 1053 1054
				(dl_time_before(p->dl.deadline,
					cpu_rq(target)->dl.earliest_dl.curr) ||
				(cpu_rq(target)->dl.dl_nr_running == 0)))
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068
			cpu = target;
	}
	rcu_read_unlock();

out:
	return cpu;
}

static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p)
{
	/*
	 * Current can't be migrated, useless to reschedule,
	 * let's hope p can move out.
	 */
1069
	if (tsk_nr_cpus_allowed(rq->curr) == 1 ||
1070
	    cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1)
1071 1072 1073 1074 1075 1076
		return;

	/*
	 * p is migratable, so let's not schedule it and
	 * see if it is pushed or pulled somewhere else.
	 */
1077
	if (tsk_nr_cpus_allowed(p) != 1 &&
1078
	    cpudl_find(&rq->rd->cpudl, p, NULL) != -1)
1079 1080
		return;

1081
	resched_curr(rq);
1082 1083 1084 1085
}

#endif /* CONFIG_SMP */

1086 1087 1088 1089 1090 1091 1092
/*
 * Only called when both the current and waking task are -deadline
 * tasks.
 */
static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
				  int flags)
{
1093
	if (dl_entity_preempt(&p->dl, &rq->curr->dl)) {
1094
		resched_curr(rq);
1095 1096 1097 1098 1099 1100 1101 1102
		return;
	}

#ifdef CONFIG_SMP
	/*
	 * In the unlikely case current and p have the same deadline
	 * let us try to decide what's the best thing to do...
	 */
1103 1104
	if ((p->dl.deadline == rq->curr->dl.deadline) &&
	    !test_tsk_need_resched(rq->curr))
1105 1106
		check_preempt_equal_dl(rq, p);
#endif /* CONFIG_SMP */
1107 1108 1109 1110 1111
}

#ifdef CONFIG_SCHED_HRTICK
static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
{
1112
	hrtick_start(rq, p->dl.runtime);
1113
}
1114 1115 1116 1117
#else /* !CONFIG_SCHED_HRTICK */
static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
{
}
1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130
#endif

static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
						   struct dl_rq *dl_rq)
{
	struct rb_node *left = dl_rq->rb_leftmost;

	if (!left)
		return NULL;

	return rb_entry(left, struct sched_dl_entity, rb_node);
}

1131 1132
struct task_struct *
pick_next_task_dl(struct rq *rq, struct task_struct *prev, struct pin_cookie cookie)
1133 1134 1135 1136 1137 1138 1139
{
	struct sched_dl_entity *dl_se;
	struct task_struct *p;
	struct dl_rq *dl_rq;

	dl_rq = &rq->dl;

1140
	if (need_pull_dl_task(rq, prev)) {
1141 1142 1143 1144 1145 1146
		/*
		 * This is OK, because current is on_cpu, which avoids it being
		 * picked for load-balance and preemption/IRQs are still
		 * disabled avoiding further scheduler activity on it and we're
		 * being very careful to re-start the picking loop.
		 */
1147
		lockdep_unpin_lock(&rq->lock, cookie);
1148
		pull_dl_task(rq);
1149
		lockdep_repin_lock(&rq->lock, cookie);
1150 1151 1152 1153 1154
		/*
		 * pull_rt_task() can drop (and re-acquire) rq->lock; this
		 * means a stop task can slip in, in which case we need to
		 * re-start task selection.
		 */
1155
		if (rq->stop && task_on_rq_queued(rq->stop))
1156 1157 1158
			return RETRY_TASK;
	}

1159 1160 1161 1162 1163 1164
	/*
	 * When prev is DL, we may throttle it in put_prev_task().
	 * So, we update time before we check for dl_nr_running.
	 */
	if (prev->sched_class == &dl_sched_class)
		update_curr_dl(rq);
1165

1166 1167 1168
	if (unlikely(!dl_rq->dl_nr_running))
		return NULL;

1169
	put_prev_task(rq, prev);
1170

1171 1172 1173 1174 1175
	dl_se = pick_next_dl_entity(rq, dl_rq);
	BUG_ON(!dl_se);

	p = dl_task_of(dl_se);
	p->se.exec_start = rq_clock_task(rq);
1176 1177

	/* Running task will never be pushed. */
1178
       dequeue_pushable_dl_task(rq, p);
1179

1180 1181
	if (hrtick_enabled(rq))
		start_hrtick_dl(rq, p);
1182

1183
	queue_push_tasks(rq);
1184

1185 1186 1187 1188 1189 1190
	return p;
}

static void put_prev_task_dl(struct rq *rq, struct task_struct *p)
{
	update_curr_dl(rq);
1191

1192
	if (on_dl_rq(&p->dl) && tsk_nr_cpus_allowed(p) > 1)
1193
		enqueue_pushable_dl_task(rq, p);
1194 1195 1196 1197 1198 1199
}

static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
{
	update_curr_dl(rq);

1200 1201 1202 1203 1204 1205 1206
	/*
	 * Even when we have runtime, update_curr_dl() might have resulted in us
	 * not being the leftmost task anymore. In that case NEED_RESCHED will
	 * be set and schedule() will start a new hrtick for the next task.
	 */
	if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
	    is_leftmost(p, &rq->dl))
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219
		start_hrtick_dl(rq, p);
}

static void task_fork_dl(struct task_struct *p)
{
	/*
	 * SCHED_DEADLINE tasks cannot fork and this is achieved through
	 * sched_fork()
	 */
}

static void task_dead_dl(struct task_struct *p)
{
1220 1221 1222 1223 1224 1225
	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));

	/*
	 * Since we are TASK_DEAD we won't slip out of the domain!
	 */
	raw_spin_lock_irq(&dl_b->lock);
1226
	/* XXX we should retain the bw until 0-lag */
1227 1228
	dl_b->total_bw -= p->dl.dl_bw;
	raw_spin_unlock_irq(&dl_b->lock);
1229 1230 1231 1232 1233 1234 1235
}

static void set_curr_task_dl(struct rq *rq)
{
	struct task_struct *p = rq->curr;

	p->se.exec_start = rq_clock_task(rq);
1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248

	/* You can't push away the running task */
	dequeue_pushable_dl_task(rq, p);
}

#ifdef CONFIG_SMP

/* Only try algorithms three times */
#define DL_MAX_TRIES 3

static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu)
{
	if (!task_running(rq, p) &&
K
Kirill Tkhai 已提交
1249
	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1250 1251 1252 1253
		return 1;
	return 0;
}

1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279
/*
 * Return the earliest pushable rq's task, which is suitable to be executed
 * on the CPU, NULL otherwise:
 */
static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu)
{
	struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost;
	struct task_struct *p = NULL;

	if (!has_pushable_dl_tasks(rq))
		return NULL;

next_node:
	if (next_node) {
		p = rb_entry(next_node, struct task_struct, pushable_dl_tasks);

		if (pick_dl_task(rq, p, cpu))
			return p;

		next_node = rb_next(next_node);
		goto next_node;
	}

	return NULL;
}

1280 1281 1282 1283 1284
static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl);

static int find_later_rq(struct task_struct *task)
{
	struct sched_domain *sd;
1285
	struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
1286 1287 1288 1289 1290 1291 1292
	int this_cpu = smp_processor_id();
	int best_cpu, cpu = task_cpu(task);

	/* Make sure the mask is initialized first */
	if (unlikely(!later_mask))
		return -1;

1293
	if (tsk_nr_cpus_allowed(task) == 1)
1294 1295
		return -1;

1296 1297 1298 1299
	/*
	 * We have to consider system topology and task affinity
	 * first, then we can look for a suitable cpu.
	 */
1300 1301
	best_cpu = cpudl_find(&task_rq(task)->rd->cpudl,
			task, later_mask);
1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382
	if (best_cpu == -1)
		return -1;

	/*
	 * If we are here, some target has been found,
	 * the most suitable of which is cached in best_cpu.
	 * This is, among the runqueues where the current tasks
	 * have later deadlines than the task's one, the rq
	 * with the latest possible one.
	 *
	 * Now we check how well this matches with task's
	 * affinity and system topology.
	 *
	 * The last cpu where the task run is our first
	 * guess, since it is most likely cache-hot there.
	 */
	if (cpumask_test_cpu(cpu, later_mask))
		return cpu;
	/*
	 * Check if this_cpu is to be skipped (i.e., it is
	 * not in the mask) or not.
	 */
	if (!cpumask_test_cpu(this_cpu, later_mask))
		this_cpu = -1;

	rcu_read_lock();
	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_AFFINE) {

			/*
			 * If possible, preempting this_cpu is
			 * cheaper than migrating.
			 */
			if (this_cpu != -1 &&
			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
				rcu_read_unlock();
				return this_cpu;
			}

			/*
			 * Last chance: if best_cpu is valid and is
			 * in the mask, that becomes our choice.
			 */
			if (best_cpu < nr_cpu_ids &&
			    cpumask_test_cpu(best_cpu, sched_domain_span(sd))) {
				rcu_read_unlock();
				return best_cpu;
			}
		}
	}
	rcu_read_unlock();

	/*
	 * At this point, all our guesses failed, we just return
	 * 'something', and let the caller sort the things out.
	 */
	if (this_cpu != -1)
		return this_cpu;

	cpu = cpumask_any(later_mask);
	if (cpu < nr_cpu_ids)
		return cpu;

	return -1;
}

/* Locks the rq it finds */
static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq)
{
	struct rq *later_rq = NULL;
	int tries;
	int cpu;

	for (tries = 0; tries < DL_MAX_TRIES; tries++) {
		cpu = find_later_rq(task);

		if ((cpu == -1) || (cpu == rq->cpu))
			break;

		later_rq = cpu_rq(cpu);

1383 1384
		if (later_rq->dl.dl_nr_running &&
		    !dl_time_before(task->dl.deadline,
1385 1386 1387 1388 1389 1390 1391 1392 1393 1394
					later_rq->dl.earliest_dl.curr)) {
			/*
			 * Target rq has tasks of equal or earlier deadline,
			 * retrying does not release any lock and is unlikely
			 * to yield a different result.
			 */
			later_rq = NULL;
			break;
		}

1395 1396 1397 1398
		/* Retry if something changed. */
		if (double_lock_balance(rq, later_rq)) {
			if (unlikely(task_rq(task) != rq ||
				     !cpumask_test_cpu(later_rq->cpu,
1399
						       tsk_cpus_allowed(task)) ||
1400
				     task_running(rq, task) ||
1401
				     !dl_task(task) ||
1402
				     !task_on_rq_queued(task))) {
1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438
				double_unlock_balance(rq, later_rq);
				later_rq = NULL;
				break;
			}
		}

		/*
		 * If the rq we found has no -deadline task, or
		 * its earliest one has a later deadline than our
		 * task, the rq is a good one.
		 */
		if (!later_rq->dl.dl_nr_running ||
		    dl_time_before(task->dl.deadline,
				   later_rq->dl.earliest_dl.curr))
			break;

		/* Otherwise we try again. */
		double_unlock_balance(rq, later_rq);
		later_rq = NULL;
	}

	return later_rq;
}

static struct task_struct *pick_next_pushable_dl_task(struct rq *rq)
{
	struct task_struct *p;

	if (!has_pushable_dl_tasks(rq))
		return NULL;

	p = rb_entry(rq->dl.pushable_dl_tasks_leftmost,
		     struct task_struct, pushable_dl_tasks);

	BUG_ON(rq->cpu != task_cpu(p));
	BUG_ON(task_current(rq, p));
1439
	BUG_ON(tsk_nr_cpus_allowed(p) <= 1);
1440

1441
	BUG_ON(!task_on_rq_queued(p));
1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455
	BUG_ON(!dl_task(p));

	return p;
}

/*
 * See if the non running -deadline tasks on this rq
 * can be sent to some other CPU where they can preempt
 * and start executing.
 */
static int push_dl_task(struct rq *rq)
{
	struct task_struct *next_task;
	struct rq *later_rq;
1456
	int ret = 0;
1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477

	if (!rq->dl.overloaded)
		return 0;

	next_task = pick_next_pushable_dl_task(rq);
	if (!next_task)
		return 0;

retry:
	if (unlikely(next_task == rq->curr)) {
		WARN_ON(1);
		return 0;
	}

	/*
	 * If next_task preempts rq->curr, and rq->curr
	 * can move away, it makes sense to just reschedule
	 * without going further in pushing next_task.
	 */
	if (dl_task(rq->curr) &&
	    dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) &&
1478
	    tsk_nr_cpus_allowed(rq->curr) > 1) {
1479
		resched_curr(rq);
1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516
		return 0;
	}

	/* We might release rq lock */
	get_task_struct(next_task);

	/* Will lock the rq it'll find */
	later_rq = find_lock_later_rq(next_task, rq);
	if (!later_rq) {
		struct task_struct *task;

		/*
		 * We must check all this again, since
		 * find_lock_later_rq releases rq->lock and it is
		 * then possible that next_task has migrated.
		 */
		task = pick_next_pushable_dl_task(rq);
		if (task_cpu(next_task) == rq->cpu && task == next_task) {
			/*
			 * The task is still there. We don't try
			 * again, some other cpu will pull it when ready.
			 */
			goto out;
		}

		if (!task)
			/* No more tasks */
			goto out;

		put_task_struct(next_task);
		next_task = task;
		goto retry;
	}

	deactivate_task(rq, next_task, 0);
	set_task_cpu(next_task, later_rq->cpu);
	activate_task(later_rq, next_task, 0);
1517
	ret = 1;
1518

1519
	resched_curr(later_rq);
1520 1521 1522 1523 1524 1525

	double_unlock_balance(rq, later_rq);

out:
	put_task_struct(next_task);

1526
	return ret;
1527 1528 1529 1530
}

static void push_dl_tasks(struct rq *rq)
{
1531
	/* push_dl_task() will return true if it moved a -deadline task */
1532 1533
	while (push_dl_task(rq))
		;
1534 1535
}

1536
static void pull_dl_task(struct rq *this_rq)
1537
{
1538
	int this_cpu = this_rq->cpu, cpu;
1539
	struct task_struct *p;
1540
	bool resched = false;
1541 1542 1543 1544
	struct rq *src_rq;
	u64 dmin = LONG_MAX;

	if (likely(!dl_overloaded(this_rq)))
1545
		return;
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577

	/*
	 * Match the barrier from dl_set_overloaded; this guarantees that if we
	 * see overloaded we must also see the dlo_mask bit.
	 */
	smp_rmb();

	for_each_cpu(cpu, this_rq->rd->dlo_mask) {
		if (this_cpu == cpu)
			continue;

		src_rq = cpu_rq(cpu);

		/*
		 * It looks racy, abd it is! However, as in sched_rt.c,
		 * we are fine with this.
		 */
		if (this_rq->dl.dl_nr_running &&
		    dl_time_before(this_rq->dl.earliest_dl.curr,
				   src_rq->dl.earliest_dl.next))
			continue;

		/* Might drop this_rq->lock */
		double_lock_balance(this_rq, src_rq);

		/*
		 * If there are no more pullable tasks on the
		 * rq, we're done with it.
		 */
		if (src_rq->dl.dl_nr_running <= 1)
			goto skip;

1578
		p = pick_earliest_pushable_dl_task(src_rq, this_cpu);
1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589

		/*
		 * We found a task to be pulled if:
		 *  - it preempts our current (if there's one),
		 *  - it will preempt the last one we pulled (if any).
		 */
		if (p && dl_time_before(p->dl.deadline, dmin) &&
		    (!this_rq->dl.dl_nr_running ||
		     dl_time_before(p->dl.deadline,
				    this_rq->dl.earliest_dl.curr))) {
			WARN_ON(p == src_rq->curr);
1590
			WARN_ON(!task_on_rq_queued(p));
1591 1592 1593 1594 1595 1596 1597 1598 1599

			/*
			 * Then we pull iff p has actually an earlier
			 * deadline than the current task of its runqueue.
			 */
			if (dl_time_before(p->dl.deadline,
					   src_rq->curr->dl.deadline))
				goto skip;

1600
			resched = true;
1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612

			deactivate_task(src_rq, p, 0);
			set_task_cpu(p, this_cpu);
			activate_task(this_rq, p, 0);
			dmin = p->dl.deadline;

			/* Is there any other task even earlier? */
		}
skip:
		double_unlock_balance(this_rq, src_rq);
	}

1613 1614
	if (resched)
		resched_curr(this_rq);
1615 1616 1617 1618 1619 1620 1621 1622 1623 1624
}

/*
 * Since the task is not running and a reschedule is not going to happen
 * anytime soon on its runqueue, we try pushing it away now.
 */
static void task_woken_dl(struct rq *rq, struct task_struct *p)
{
	if (!task_running(rq, p) &&
	    !test_tsk_need_resched(rq->curr) &&
1625
	    tsk_nr_cpus_allowed(p) > 1 &&
1626
	    dl_task(rq->curr) &&
1627
	    (tsk_nr_cpus_allowed(rq->curr) < 2 ||
1628
	     !dl_entity_preempt(&p->dl, &rq->curr->dl))) {
1629 1630 1631 1632 1633 1634 1635
		push_dl_tasks(rq);
	}
}

static void set_cpus_allowed_dl(struct task_struct *p,
				const struct cpumask *new_mask)
{
1636
	struct root_domain *src_rd;
1637
	struct rq *rq;
1638 1639 1640

	BUG_ON(!dl_task(p));

1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662
	rq = task_rq(p);
	src_rd = rq->rd;
	/*
	 * Migrating a SCHED_DEADLINE task between exclusive
	 * cpusets (different root_domains) entails a bandwidth
	 * update. We already made space for us in the destination
	 * domain (see cpuset_can_attach()).
	 */
	if (!cpumask_intersects(src_rd->span, new_mask)) {
		struct dl_bw *src_dl_b;

		src_dl_b = dl_bw_of(cpu_of(rq));
		/*
		 * We now free resources of the root_domain we are migrating
		 * off. In the worst case, sched_setattr() may temporary fail
		 * until we complete the update.
		 */
		raw_spin_lock(&src_dl_b->lock);
		__dl_clear(src_dl_b, p->dl.dl_bw);
		raw_spin_unlock(&src_dl_b->lock);
	}

1663
	set_cpus_allowed_common(p, new_mask);
1664 1665 1666 1667 1668 1669 1670
}

/* Assumes rq->lock is held */
static void rq_online_dl(struct rq *rq)
{
	if (rq->dl.overloaded)
		dl_set_overload(rq);
1671

1672
	cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu);
1673
	if (rq->dl.dl_nr_running > 0)
1674
		cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr);
1675 1676 1677 1678 1679 1680 1681
}

/* Assumes rq->lock is held */
static void rq_offline_dl(struct rq *rq)
{
	if (rq->dl.overloaded)
		dl_clear_overload(rq);
1682

1683
	cpudl_clear(&rq->rd->cpudl, rq->cpu);
1684
	cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu);
1685 1686
}

1687
void __init init_sched_dl_class(void)
1688 1689 1690 1691 1692 1693 1694 1695 1696 1697
{
	unsigned int i;

	for_each_possible_cpu(i)
		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i),
					GFP_KERNEL, cpu_to_node(i));
}

#endif /* CONFIG_SMP */

1698 1699
static void switched_from_dl(struct rq *rq, struct task_struct *p)
{
1700 1701 1702 1703 1704 1705 1706 1707
	/*
	 * Start the deadline timer; if we switch back to dl before this we'll
	 * continue consuming our current CBS slice. If we stay outside of
	 * SCHED_DEADLINE until the deadline passes, the timer will reset the
	 * task.
	 */
	if (!start_dl_timer(p))
		__dl_clear_params(p);
1708

1709 1710 1711 1712 1713
	/*
	 * Since this might be the only -deadline task on the rq,
	 * this is the right place to try to pull some other one
	 * from an overloaded cpu, if any.
	 */
1714 1715 1716
	if (!task_on_rq_queued(p) || rq->dl.dl_nr_running)
		return;

1717
	queue_pull_task(rq);
1718 1719
}

1720 1721 1722 1723
/*
 * When switching to -deadline, we may overload the rq, then
 * we try to push someone off, if possible.
 */
1724 1725
static void switched_to_dl(struct rq *rq, struct task_struct *p)
{
1726 1727 1728 1729 1730 1731 1732 1733 1734 1735

	/* If p is not queued we will update its parameters at next wakeup. */
	if (!task_on_rq_queued(p))
		return;

	/*
	 * If p is boosted we already updated its params in
	 * rt_mutex_setprio()->enqueue_task(..., ENQUEUE_REPLENISH),
	 * p's deadline being now already after rq_clock(rq).
	 */
1736
	if (dl_time_before(p->dl.deadline, rq_clock(rq)))
1737
		setup_new_dl_entity(&p->dl);
1738

1739
	if (rq->curr != p) {
1740
#ifdef CONFIG_SMP
1741
		if (tsk_nr_cpus_allowed(p) > 1 && rq->dl.overloaded)
1742 1743 1744 1745 1746 1747 1748
			queue_push_tasks(rq);
#else
		if (dl_task(rq->curr))
			check_preempt_curr_dl(rq, p, 0);
		else
			resched_curr(rq);
#endif
1749 1750 1751
	}
}

1752 1753 1754 1755
/*
 * If the scheduling parameters of a -deadline task changed,
 * a push or pull operation might be needed.
 */
1756 1757 1758
static void prio_changed_dl(struct rq *rq, struct task_struct *p,
			    int oldprio)
{
1759
	if (task_on_rq_queued(p) || rq->curr == p) {
1760
#ifdef CONFIG_SMP
1761 1762 1763 1764 1765 1766 1767
		/*
		 * This might be too much, but unfortunately
		 * we don't have the old deadline value, and
		 * we can't argue if the task is increasing
		 * or lowering its prio, so...
		 */
		if (!rq->dl.overloaded)
1768
			queue_pull_task(rq);
1769 1770 1771 1772 1773 1774

		/*
		 * If we now have a earlier deadline task than p,
		 * then reschedule, provided p is still on this
		 * runqueue.
		 */
1775
		if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline))
1776
			resched_curr(rq);
1777 1778 1779 1780 1781 1782
#else
		/*
		 * Again, we don't know if p has a earlier
		 * or later deadline, so let's blindly set a
		 * (maybe not needed) rescheduling point.
		 */
1783
		resched_curr(rq);
1784
#endif /* CONFIG_SMP */
1785
	}
1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800
}

const struct sched_class dl_sched_class = {
	.next			= &rt_sched_class,
	.enqueue_task		= enqueue_task_dl,
	.dequeue_task		= dequeue_task_dl,
	.yield_task		= yield_task_dl,

	.check_preempt_curr	= check_preempt_curr_dl,

	.pick_next_task		= pick_next_task_dl,
	.put_prev_task		= put_prev_task_dl,

#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_dl,
1801 1802 1803 1804
	.set_cpus_allowed       = set_cpus_allowed_dl,
	.rq_online              = rq_online_dl,
	.rq_offline             = rq_offline_dl,
	.task_woken		= task_woken_dl,
1805 1806 1807 1808 1809 1810 1811 1812 1813 1814
#endif

	.set_curr_task		= set_curr_task_dl,
	.task_tick		= task_tick_dl,
	.task_fork              = task_fork_dl,
	.task_dead		= task_dead_dl,

	.prio_changed           = prio_changed_dl,
	.switched_from		= switched_from_dl,
	.switched_to		= switched_to_dl,
1815 1816

	.update_curr		= update_curr_dl,
1817
};
1818 1819 1820 1821 1822 1823 1824 1825 1826

#ifdef CONFIG_SCHED_DEBUG
extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);

void print_dl_stats(struct seq_file *m, int cpu)
{
	print_dl_rq(m, cpu, &cpu_rq(cpu)->dl);
}
#endif /* CONFIG_SCHED_DEBUG */