rt.c 45.7 KB
Newer Older
I
Ingo Molnar 已提交
1 2 3 4 5
/*
 * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR
 * policies)
 */

6 7 8 9
#include "sched.h"

#include <linux/slab.h>

10 11
int sched_rr_timeslice = RR_TIMESLICE;

12 13 14 15 16 17 18 19 20 21 22 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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);

struct rt_bandwidth def_rt_bandwidth;

static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
{
	struct rt_bandwidth *rt_b =
		container_of(timer, struct rt_bandwidth, rt_period_timer);
	ktime_t now;
	int overrun;
	int idle = 0;

	for (;;) {
		now = hrtimer_cb_get_time(timer);
		overrun = hrtimer_forward(timer, now, rt_b->rt_period);

		if (!overrun)
			break;

		idle = do_sched_rt_period_timer(rt_b, overrun);
	}

	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
}

void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
{
	rt_b->rt_period = ns_to_ktime(period);
	rt_b->rt_runtime = runtime;

	raw_spin_lock_init(&rt_b->rt_runtime_lock);

	hrtimer_init(&rt_b->rt_period_timer,
			CLOCK_MONOTONIC, HRTIMER_MODE_REL);
	rt_b->rt_period_timer.function = sched_rt_period_timer;
}

static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
{
	if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
		return;

	if (hrtimer_active(&rt_b->rt_period_timer))
		return;

	raw_spin_lock(&rt_b->rt_runtime_lock);
	start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period);
	raw_spin_unlock(&rt_b->rt_runtime_lock);
}

void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
{
	struct rt_prio_array *array;
	int i;

	array = &rt_rq->active;
	for (i = 0; i < MAX_RT_PRIO; i++) {
		INIT_LIST_HEAD(array->queue + i);
		__clear_bit(i, array->bitmap);
	}
	/* delimiter for bitsearch: */
	__set_bit(MAX_RT_PRIO, array->bitmap);

#if defined CONFIG_SMP
	rt_rq->highest_prio.curr = MAX_RT_PRIO;
	rt_rq->highest_prio.next = MAX_RT_PRIO;
	rt_rq->rt_nr_migratory = 0;
	rt_rq->overloaded = 0;
	plist_head_init(&rt_rq->pushable_tasks);
#endif

	rt_rq->rt_time = 0;
	rt_rq->rt_throttled = 0;
	rt_rq->rt_runtime = 0;
	raw_spin_lock_init(&rt_rq->rt_runtime_lock);
}

89
#ifdef CONFIG_RT_GROUP_SCHED
90 91 92 93
static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
{
	hrtimer_cancel(&rt_b->rt_period_timer);
}
94 95 96

#define rt_entity_is_task(rt_se) (!(rt_se)->my_q)

97 98
static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
{
99 100 101
#ifdef CONFIG_SCHED_DEBUG
	WARN_ON_ONCE(!rt_entity_is_task(rt_se));
#endif
102 103 104 105 106 107 108 109 110 111 112 113 114
	return container_of(rt_se, struct task_struct, rt);
}

static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
{
	return rt_rq->rq;
}

static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
{
	return rt_se->rt_rq;
}

115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 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 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
void free_rt_sched_group(struct task_group *tg)
{
	int i;

	if (tg->rt_se)
		destroy_rt_bandwidth(&tg->rt_bandwidth);

	for_each_possible_cpu(i) {
		if (tg->rt_rq)
			kfree(tg->rt_rq[i]);
		if (tg->rt_se)
			kfree(tg->rt_se[i]);
	}

	kfree(tg->rt_rq);
	kfree(tg->rt_se);
}

void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
		struct sched_rt_entity *rt_se, int cpu,
		struct sched_rt_entity *parent)
{
	struct rq *rq = cpu_rq(cpu);

	rt_rq->highest_prio.curr = MAX_RT_PRIO;
	rt_rq->rt_nr_boosted = 0;
	rt_rq->rq = rq;
	rt_rq->tg = tg;

	tg->rt_rq[cpu] = rt_rq;
	tg->rt_se[cpu] = rt_se;

	if (!rt_se)
		return;

	if (!parent)
		rt_se->rt_rq = &rq->rt;
	else
		rt_se->rt_rq = parent->my_q;

	rt_se->my_q = rt_rq;
	rt_se->parent = parent;
	INIT_LIST_HEAD(&rt_se->run_list);
}

int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
{
	struct rt_rq *rt_rq;
	struct sched_rt_entity *rt_se;
	int i;

	tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL);
	if (!tg->rt_rq)
		goto err;
	tg->rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL);
	if (!tg->rt_se)
		goto err;

	init_rt_bandwidth(&tg->rt_bandwidth,
			ktime_to_ns(def_rt_bandwidth.rt_period), 0);

	for_each_possible_cpu(i) {
		rt_rq = kzalloc_node(sizeof(struct rt_rq),
				     GFP_KERNEL, cpu_to_node(i));
		if (!rt_rq)
			goto err;

		rt_se = kzalloc_node(sizeof(struct sched_rt_entity),
				     GFP_KERNEL, cpu_to_node(i));
		if (!rt_se)
			goto err_free_rq;

		init_rt_rq(rt_rq, cpu_rq(i));
		rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
		init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]);
	}

	return 1;

err_free_rq:
	kfree(rt_rq);
err:
	return 0;
}

200 201
#else /* CONFIG_RT_GROUP_SCHED */

202 203
#define rt_entity_is_task(rt_se) (1)

204 205 206 207 208
static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
{
	return container_of(rt_se, struct task_struct, rt);
}

209 210 211 212 213 214 215 216 217 218 219 220 221
static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
{
	return container_of(rt_rq, struct rq, rt);
}

static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
{
	struct task_struct *p = rt_task_of(rt_se);
	struct rq *rq = task_rq(p);

	return &rq->rt;
}

222 223 224 225 226 227
void free_rt_sched_group(struct task_group *tg) { }

int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
{
	return 1;
}
228 229
#endif /* CONFIG_RT_GROUP_SCHED */

S
Steven Rostedt 已提交
230
#ifdef CONFIG_SMP
I
Ingo Molnar 已提交
231

232 233
static int pull_rt_task(struct rq *this_rq);

234
static inline int rt_overloaded(struct rq *rq)
S
Steven Rostedt 已提交
235
{
236
	return atomic_read(&rq->rd->rto_count);
S
Steven Rostedt 已提交
237
}
I
Ingo Molnar 已提交
238

S
Steven Rostedt 已提交
239 240
static inline void rt_set_overload(struct rq *rq)
{
241 242 243
	if (!rq->online)
		return;

244
	cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
S
Steven Rostedt 已提交
245 246 247 248 249 250
	/*
	 * Make sure the mask is visible before we set
	 * the overload count. That is checked to determine
	 * if we should look at the mask. It would be a shame
	 * if we looked at the mask, but the mask was not
	 * updated yet.
P
Peter Zijlstra 已提交
251 252
	 *
	 * Matched by the barrier in pull_rt_task().
S
Steven Rostedt 已提交
253
	 */
P
Peter Zijlstra 已提交
254
	smp_wmb();
255
	atomic_inc(&rq->rd->rto_count);
S
Steven Rostedt 已提交
256
}
I
Ingo Molnar 已提交
257

S
Steven Rostedt 已提交
258 259
static inline void rt_clear_overload(struct rq *rq)
{
260 261 262
	if (!rq->online)
		return;

S
Steven Rostedt 已提交
263
	/* the order here really doesn't matter */
264
	atomic_dec(&rq->rd->rto_count);
265
	cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
S
Steven Rostedt 已提交
266
}
267

268
static void update_rt_migration(struct rt_rq *rt_rq)
269
{
270
	if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) {
271 272 273
		if (!rt_rq->overloaded) {
			rt_set_overload(rq_of_rt_rq(rt_rq));
			rt_rq->overloaded = 1;
274
		}
275 276 277
	} else if (rt_rq->overloaded) {
		rt_clear_overload(rq_of_rt_rq(rt_rq));
		rt_rq->overloaded = 0;
278
	}
279
}
S
Steven Rostedt 已提交
280

281 282
static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
283 284
	struct task_struct *p;

285 286 287
	if (!rt_entity_is_task(rt_se))
		return;

288
	p = rt_task_of(rt_se);
289 290 291
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total++;
292
	if (p->nr_cpus_allowed > 1)
293 294 295 296 297 298 299
		rt_rq->rt_nr_migratory++;

	update_rt_migration(rt_rq);
}

static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
300 301
	struct task_struct *p;

302 303 304
	if (!rt_entity_is_task(rt_se))
		return;

305
	p = rt_task_of(rt_se);
306 307 308
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total--;
309
	if (p->nr_cpus_allowed > 1)
310 311 312 313 314
		rt_rq->rt_nr_migratory--;

	update_rt_migration(rt_rq);
}

315 316 317 318 319
static inline int has_pushable_tasks(struct rq *rq)
{
	return !plist_head_empty(&rq->rt.pushable_tasks);
}

320 321 322 323 324
static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
{
	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
	plist_node_init(&p->pushable_tasks, p->prio);
	plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);
325 326 327 328

	/* Update the highest prio pushable task */
	if (p->prio < rq->rt.highest_prio.next)
		rq->rt.highest_prio.next = p->prio;
329 330 331 332 333 334
}

static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
{
	plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);

335 336 337 338 339 340 341
	/* Update the new highest prio pushable task */
	if (has_pushable_tasks(rq)) {
		p = plist_first_entry(&rq->rt.pushable_tasks,
				      struct task_struct, pushable_tasks);
		rq->rt.highest_prio.next = p->prio;
	} else
		rq->rt.highest_prio.next = MAX_RT_PRIO;
342 343
}

344 345
#else

346
static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
P
Peter Zijlstra 已提交
347
{
P
Peter Zijlstra 已提交
348 349
}

350 351 352 353
static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
{
}

354
static inline
355 356 357 358
void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
}

359
static inline
360 361 362
void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
}
363

S
Steven Rostedt 已提交
364 365
#endif /* CONFIG_SMP */

P
Peter Zijlstra 已提交
366 367 368 369 370
static inline int on_rt_rq(struct sched_rt_entity *rt_se)
{
	return !list_empty(&rt_se->run_list);
}

371
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
372

P
Peter Zijlstra 已提交
373
static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
374 375
{
	if (!rt_rq->tg)
P
Peter Zijlstra 已提交
376
		return RUNTIME_INF;
P
Peter Zijlstra 已提交
377

P
Peter Zijlstra 已提交
378 379 380 381 382 383
	return rt_rq->rt_runtime;
}

static inline u64 sched_rt_period(struct rt_rq *rt_rq)
{
	return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period);
P
Peter Zijlstra 已提交
384 385
}

C
Cheng Xu 已提交
386 387
typedef struct task_group *rt_rq_iter_t;

388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
static inline struct task_group *next_task_group(struct task_group *tg)
{
	do {
		tg = list_entry_rcu(tg->list.next,
			typeof(struct task_group), list);
	} while (&tg->list != &task_groups && task_group_is_autogroup(tg));

	if (&tg->list == &task_groups)
		tg = NULL;

	return tg;
}

#define for_each_rt_rq(rt_rq, iter, rq)					\
	for (iter = container_of(&task_groups, typeof(*iter), list);	\
		(iter = next_task_group(iter)) &&			\
		(rt_rq = iter->rt_rq[cpu_of(rq)]);)
C
Cheng Xu 已提交
405

P
Peter Zijlstra 已提交
406 407 408 409 410 411 412 413
#define for_each_sched_rt_entity(rt_se) \
	for (; rt_se; rt_se = rt_se->parent)

static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
{
	return rt_se->my_q;
}

414
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
P
Peter Zijlstra 已提交
415 416
static void dequeue_rt_entity(struct sched_rt_entity *rt_se);

P
Peter Zijlstra 已提交
417
static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
418
{
419
	struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
420 421
	struct sched_rt_entity *rt_se;

422 423 424
	int cpu = cpu_of(rq_of_rt_rq(rt_rq));

	rt_se = rt_rq->tg->rt_se[cpu];
P
Peter Zijlstra 已提交
425

426 427
	if (rt_rq->rt_nr_running) {
		if (rt_se && !on_rt_rq(rt_se))
428
			enqueue_rt_entity(rt_se, false);
429
		if (rt_rq->highest_prio.curr < curr->prio)
430
			resched_task(curr);
P
Peter Zijlstra 已提交
431 432 433
	}
}

P
Peter Zijlstra 已提交
434
static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
435
{
436
	struct sched_rt_entity *rt_se;
437
	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
438

439
	rt_se = rt_rq->tg->rt_se[cpu];
P
Peter Zijlstra 已提交
440 441 442 443 444

	if (rt_se && on_rt_rq(rt_se))
		dequeue_rt_entity(rt_se);
}

P
Peter Zijlstra 已提交
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461
static inline int rt_rq_throttled(struct rt_rq *rt_rq)
{
	return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
}

static int rt_se_boosted(struct sched_rt_entity *rt_se)
{
	struct rt_rq *rt_rq = group_rt_rq(rt_se);
	struct task_struct *p;

	if (rt_rq)
		return !!rt_rq->rt_nr_boosted;

	p = rt_task_of(rt_se);
	return p->prio != p->normal_prio;
}

462
#ifdef CONFIG_SMP
463
static inline const struct cpumask *sched_rt_period_mask(void)
464
{
N
Nathan Zimmer 已提交
465
	return this_rq()->rd->span;
466
}
P
Peter Zijlstra 已提交
467
#else
468
static inline const struct cpumask *sched_rt_period_mask(void)
469
{
470
	return cpu_online_mask;
471 472
}
#endif
P
Peter Zijlstra 已提交
473

474 475
static inline
struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
P
Peter Zijlstra 已提交
476
{
477 478
	return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
}
P
Peter Zijlstra 已提交
479

P
Peter Zijlstra 已提交
480 481 482 483 484
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &rt_rq->tg->rt_bandwidth;
}

485
#else /* !CONFIG_RT_GROUP_SCHED */
486 487 488

static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
{
P
Peter Zijlstra 已提交
489 490 491 492 493 494
	return rt_rq->rt_runtime;
}

static inline u64 sched_rt_period(struct rt_rq *rt_rq)
{
	return ktime_to_ns(def_rt_bandwidth.rt_period);
P
Peter Zijlstra 已提交
495 496
}

C
Cheng Xu 已提交
497 498 499 500 501
typedef struct rt_rq *rt_rq_iter_t;

#define for_each_rt_rq(rt_rq, iter, rq) \
	for ((void) iter, rt_rq = &rq->rt; rt_rq; rt_rq = NULL)

P
Peter Zijlstra 已提交
502 503 504 505 506 507 508 509
#define for_each_sched_rt_entity(rt_se) \
	for (; rt_se; rt_se = NULL)

static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se)
{
	return NULL;
}

P
Peter Zijlstra 已提交
510
static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
511
{
512 513
	if (rt_rq->rt_nr_running)
		resched_task(rq_of_rt_rq(rt_rq)->curr);
P
Peter Zijlstra 已提交
514 515
}

P
Peter Zijlstra 已提交
516
static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
517 518 519
{
}

P
Peter Zijlstra 已提交
520 521 522 523
static inline int rt_rq_throttled(struct rt_rq *rt_rq)
{
	return rt_rq->rt_throttled;
}
524

525
static inline const struct cpumask *sched_rt_period_mask(void)
526
{
527
	return cpu_online_mask;
528 529 530 531 532 533 534 535
}

static inline
struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
{
	return &cpu_rq(cpu)->rt;
}

P
Peter Zijlstra 已提交
536 537 538 539 540
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &def_rt_bandwidth;
}

541
#endif /* CONFIG_RT_GROUP_SCHED */
542

P
Peter Zijlstra 已提交
543
#ifdef CONFIG_SMP
544 545 546
/*
 * We ran out of runtime, see if we can borrow some from our neighbours.
 */
547
static int do_balance_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
548 549
{
	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
550
	struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd;
P
Peter Zijlstra 已提交
551 552 553
	int i, weight, more = 0;
	u64 rt_period;

554
	weight = cpumask_weight(rd->span);
P
Peter Zijlstra 已提交
555

556
	raw_spin_lock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
557
	rt_period = ktime_to_ns(rt_b->rt_period);
558
	for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
559 560 561 562 563 564
		struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
		s64 diff;

		if (iter == rt_rq)
			continue;

565
		raw_spin_lock(&iter->rt_runtime_lock);
566 567 568 569 570
		/*
		 * Either all rqs have inf runtime and there's nothing to steal
		 * or __disable_runtime() below sets a specific rq to inf to
		 * indicate its been disabled and disalow stealing.
		 */
P
Peter Zijlstra 已提交
571 572 573
		if (iter->rt_runtime == RUNTIME_INF)
			goto next;

574 575 576 577
		/*
		 * From runqueues with spare time, take 1/n part of their
		 * spare time, but no more than our period.
		 */
P
Peter Zijlstra 已提交
578 579
		diff = iter->rt_runtime - iter->rt_time;
		if (diff > 0) {
580
			diff = div_u64((u64)diff, weight);
P
Peter Zijlstra 已提交
581 582 583 584 585 586
			if (rt_rq->rt_runtime + diff > rt_period)
				diff = rt_period - rt_rq->rt_runtime;
			iter->rt_runtime -= diff;
			rt_rq->rt_runtime += diff;
			more = 1;
			if (rt_rq->rt_runtime == rt_period) {
587
				raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
588 589 590
				break;
			}
		}
P
Peter Zijlstra 已提交
591
next:
592
		raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
593
	}
594
	raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
595 596 597

	return more;
}
P
Peter Zijlstra 已提交
598

599 600 601
/*
 * Ensure this RQ takes back all the runtime it lend to its neighbours.
 */
P
Peter Zijlstra 已提交
602 603 604
static void __disable_runtime(struct rq *rq)
{
	struct root_domain *rd = rq->rd;
C
Cheng Xu 已提交
605
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
606 607 608 609 610
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

C
Cheng Xu 已提交
611
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
612 613 614 615
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
		s64 want;
		int i;

616 617
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
618 619 620 621 622
		/*
		 * Either we're all inf and nobody needs to borrow, or we're
		 * already disabled and thus have nothing to do, or we have
		 * exactly the right amount of runtime to take out.
		 */
P
Peter Zijlstra 已提交
623 624 625
		if (rt_rq->rt_runtime == RUNTIME_INF ||
				rt_rq->rt_runtime == rt_b->rt_runtime)
			goto balanced;
626
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
627

628 629 630 631 632
		/*
		 * Calculate the difference between what we started out with
		 * and what we current have, that's the amount of runtime
		 * we lend and now have to reclaim.
		 */
P
Peter Zijlstra 已提交
633 634
		want = rt_b->rt_runtime - rt_rq->rt_runtime;

635 636 637
		/*
		 * Greedy reclaim, take back as much as we can.
		 */
638
		for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
639 640 641
			struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
			s64 diff;

642 643 644
			/*
			 * Can't reclaim from ourselves or disabled runqueues.
			 */
645
			if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
P
Peter Zijlstra 已提交
646 647
				continue;

648
			raw_spin_lock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
649 650 651 652 653 654 655 656
			if (want > 0) {
				diff = min_t(s64, iter->rt_runtime, want);
				iter->rt_runtime -= diff;
				want -= diff;
			} else {
				iter->rt_runtime -= want;
				want -= want;
			}
657
			raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
658 659 660 661 662

			if (!want)
				break;
		}

663
		raw_spin_lock(&rt_rq->rt_runtime_lock);
664 665 666 667
		/*
		 * We cannot be left wanting - that would mean some runtime
		 * leaked out of the system.
		 */
P
Peter Zijlstra 已提交
668 669
		BUG_ON(want);
balanced:
670 671 672 673
		/*
		 * Disable all the borrow logic by pretending we have inf
		 * runtime - in which case borrowing doesn't make sense.
		 */
P
Peter Zijlstra 已提交
674
		rt_rq->rt_runtime = RUNTIME_INF;
675
		rt_rq->rt_throttled = 0;
676 677
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
678 679 680 681 682
	}
}

static void __enable_runtime(struct rq *rq)
{
C
Cheng Xu 已提交
683
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
684 685 686 687 688
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

689 690 691
	/*
	 * Reset each runqueue's bandwidth settings
	 */
C
Cheng Xu 已提交
692
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
693 694
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

695 696
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
697 698
		rt_rq->rt_runtime = rt_b->rt_runtime;
		rt_rq->rt_time = 0;
699
		rt_rq->rt_throttled = 0;
700 701
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
702 703 704
	}
}

705 706 707 708
static int balance_runtime(struct rt_rq *rt_rq)
{
	int more = 0;

709 710 711
	if (!sched_feat(RT_RUNTIME_SHARE))
		return more;

712
	if (rt_rq->rt_time > rt_rq->rt_runtime) {
713
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
714
		more = do_balance_runtime(rt_rq);
715
		raw_spin_lock(&rt_rq->rt_runtime_lock);
716 717 718 719
	}

	return more;
}
720
#else /* !CONFIG_SMP */
721 722 723 724
static inline int balance_runtime(struct rt_rq *rt_rq)
{
	return 0;
}
725
#endif /* CONFIG_SMP */
P
Peter Zijlstra 已提交
726

727 728
static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
{
729
	int i, idle = 1, throttled = 0;
730
	const struct cpumask *span;
731 732

	span = sched_rt_period_mask();
733 734 735 736 737 738 739 740 741 742 743 744 745
#ifdef CONFIG_RT_GROUP_SCHED
	/*
	 * FIXME: isolated CPUs should really leave the root task group,
	 * whether they are isolcpus or were isolated via cpusets, lest
	 * the timer run on a CPU which does not service all runqueues,
	 * potentially leaving other CPUs indefinitely throttled.  If
	 * isolation is really required, the user will turn the throttle
	 * off to kill the perturbations it causes anyway.  Meanwhile,
	 * this maintains functionality for boot and/or troubleshooting.
	 */
	if (rt_b == &root_task_group.rt_bandwidth)
		span = cpu_online_mask;
#endif
746
	for_each_cpu(i, span) {
747 748 749 750
		int enqueue = 0;
		struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
		struct rq *rq = rq_of_rt_rq(rt_rq);

751
		raw_spin_lock(&rq->lock);
752 753 754
		if (rt_rq->rt_time) {
			u64 runtime;

755
			raw_spin_lock(&rt_rq->rt_runtime_lock);
756 757 758 759 760 761 762
			if (rt_rq->rt_throttled)
				balance_runtime(rt_rq);
			runtime = rt_rq->rt_runtime;
			rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
			if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
				rt_rq->rt_throttled = 0;
				enqueue = 1;
763 764 765 766 767 768 769

				/*
				 * Force a clock update if the CPU was idle,
				 * lest wakeup -> unthrottle time accumulate.
				 */
				if (rt_rq->rt_nr_running && rq->curr == rq->idle)
					rq->skip_clock_update = -1;
770 771 772
			}
			if (rt_rq->rt_time || rt_rq->rt_nr_running)
				idle = 0;
773
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
774
		} else if (rt_rq->rt_nr_running) {
775
			idle = 0;
776 777 778
			if (!rt_rq_throttled(rt_rq))
				enqueue = 1;
		}
779 780
		if (rt_rq->rt_throttled)
			throttled = 1;
781 782 783

		if (enqueue)
			sched_rt_rq_enqueue(rt_rq);
784
		raw_spin_unlock(&rq->lock);
785 786
	}

787 788 789
	if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
		return 1;

790 791
	return idle;
}
P
Peter Zijlstra 已提交
792

P
Peter Zijlstra 已提交
793 794
static inline int rt_se_prio(struct sched_rt_entity *rt_se)
{
795
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
796 797 798
	struct rt_rq *rt_rq = group_rt_rq(rt_se);

	if (rt_rq)
799
		return rt_rq->highest_prio.curr;
P
Peter Zijlstra 已提交
800 801 802 803 804
#endif

	return rt_task_of(rt_se)->prio;
}

P
Peter Zijlstra 已提交
805
static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
806
{
P
Peter Zijlstra 已提交
807
	u64 runtime = sched_rt_runtime(rt_rq);
P
Peter Zijlstra 已提交
808 809

	if (rt_rq->rt_throttled)
P
Peter Zijlstra 已提交
810
		return rt_rq_throttled(rt_rq);
P
Peter Zijlstra 已提交
811

812
	if (runtime >= sched_rt_period(rt_rq))
P
Peter Zijlstra 已提交
813 814
		return 0;

815 816 817 818
	balance_runtime(rt_rq);
	runtime = sched_rt_runtime(rt_rq);
	if (runtime == RUNTIME_INF)
		return 0;
P
Peter Zijlstra 已提交
819

P
Peter Zijlstra 已提交
820
	if (rt_rq->rt_time > runtime) {
821 822 823 824 825 826 827
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

		/*
		 * Don't actually throttle groups that have no runtime assigned
		 * but accrue some time due to boosting.
		 */
		if (likely(rt_b->rt_runtime)) {
828 829
			static bool once = false;

830
			rt_rq->rt_throttled = 1;
831 832 833 834 835

			if (!once) {
				once = true;
				printk_sched("sched: RT throttling activated\n");
			}
836 837 838 839 840 841 842 843 844
		} else {
			/*
			 * In case we did anyway, make it go away,
			 * replenishment is a joke, since it will replenish us
			 * with exactly 0 ns.
			 */
			rt_rq->rt_time = 0;
		}

P
Peter Zijlstra 已提交
845
		if (rt_rq_throttled(rt_rq)) {
P
Peter Zijlstra 已提交
846
			sched_rt_rq_dequeue(rt_rq);
P
Peter Zijlstra 已提交
847 848
			return 1;
		}
P
Peter Zijlstra 已提交
849 850 851 852 853
	}

	return 0;
}

I
Ingo Molnar 已提交
854 855 856 857
/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
A
Alexey Dobriyan 已提交
858
static void update_curr_rt(struct rq *rq)
I
Ingo Molnar 已提交
859 860
{
	struct task_struct *curr = rq->curr;
P
Peter Zijlstra 已提交
861 862
	struct sched_rt_entity *rt_se = &curr->rt;
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
I
Ingo Molnar 已提交
863 864
	u64 delta_exec;

P
Peter Zijlstra 已提交
865
	if (curr->sched_class != &rt_sched_class)
I
Ingo Molnar 已提交
866 867
		return;

868
	delta_exec = rq_clock_task(rq) - curr->se.exec_start;
869 870
	if (unlikely((s64)delta_exec <= 0))
		return;
I
Ingo Molnar 已提交
871

872 873
	schedstat_set(curr->se.statistics.exec_max,
		      max(curr->se.statistics.exec_max, delta_exec));
I
Ingo Molnar 已提交
874 875

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

878
	curr->se.exec_start = rq_clock_task(rq);
879
	cpuacct_charge(curr, delta_exec);
P
Peter Zijlstra 已提交
880

881 882
	sched_rt_avg_update(rq, delta_exec);

883 884 885
	if (!rt_bandwidth_enabled())
		return;

D
Dhaval Giani 已提交
886 887 888
	for_each_sched_rt_entity(rt_se) {
		rt_rq = rt_rq_of_se(rt_se);

889
		if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
890
			raw_spin_lock(&rt_rq->rt_runtime_lock);
891 892 893
			rt_rq->rt_time += delta_exec;
			if (sched_rt_runtime_exceeded(rt_rq))
				resched_task(curr);
894
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
895
		}
D
Dhaval Giani 已提交
896
	}
I
Ingo Molnar 已提交
897 898
}

899
#if defined CONFIG_SMP
900

901 902
static void
inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
903
{
G
Gregory Haskins 已提交
904
	struct rq *rq = rq_of_rt_rq(rt_rq);
905

906 907 908 909 910 911 912
#ifdef CONFIG_RT_GROUP_SCHED
	/*
	 * Change rq's cpupri only if rt_rq is the top queue.
	 */
	if (&rq->rt != rt_rq)
		return;
#endif
913 914
	if (rq->online && prio < prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
915
}
916

917 918 919 920
static void
dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
{
	struct rq *rq = rq_of_rt_rq(rt_rq);
921

922 923 924 925 926 927 928
#ifdef CONFIG_RT_GROUP_SCHED
	/*
	 * Change rq's cpupri only if rt_rq is the top queue.
	 */
	if (&rq->rt != rt_rq)
		return;
#endif
929 930
	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
931 932
}

933 934
#else /* CONFIG_SMP */

P
Peter Zijlstra 已提交
935
static inline
936 937 938 939 940
void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}
static inline
void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {}

#endif /* CONFIG_SMP */
941

942
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958
static void
inc_rt_prio(struct rt_rq *rt_rq, int prio)
{
	int prev_prio = rt_rq->highest_prio.curr;

	if (prio < prev_prio)
		rt_rq->highest_prio.curr = prio;

	inc_rt_prio_smp(rt_rq, prio, prev_prio);
}

static void
dec_rt_prio(struct rt_rq *rt_rq, int prio)
{
	int prev_prio = rt_rq->highest_prio.curr;

P
Peter Zijlstra 已提交
959
	if (rt_rq->rt_nr_running) {
960

961
		WARN_ON(prio < prev_prio);
962

963
		/*
964 965
		 * This may have been our highest task, and therefore
		 * we may have some recomputation to do
966
		 */
967
		if (prio == prev_prio) {
968 969 970
			struct rt_prio_array *array = &rt_rq->active;

			rt_rq->highest_prio.curr =
971
				sched_find_first_bit(array->bitmap);
972 973
		}

974
	} else
975
		rt_rq->highest_prio.curr = MAX_RT_PRIO;
976

977 978
	dec_rt_prio_smp(rt_rq, prio, prev_prio);
}
979

980 981 982 983 984 985
#else

static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {}
static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {}

#endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */
986

987
#ifdef CONFIG_RT_GROUP_SCHED
988 989 990 991 992 993 994 995 996 997 998 999 1000 1001

static void
inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
	if (rt_se_boosted(rt_se))
		rt_rq->rt_nr_boosted++;

	if (rt_rq->tg)
		start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
}

static void
dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
P
Peter Zijlstra 已提交
1002 1003 1004 1005
	if (rt_se_boosted(rt_se))
		rt_rq->rt_nr_boosted--;

	WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043
}

#else /* CONFIG_RT_GROUP_SCHED */

static void
inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
	start_rt_bandwidth(&def_rt_bandwidth);
}

static inline
void dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) {}

#endif /* CONFIG_RT_GROUP_SCHED */

static inline
void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
	int prio = rt_se_prio(rt_se);

	WARN_ON(!rt_prio(prio));
	rt_rq->rt_nr_running++;

	inc_rt_prio(rt_rq, prio);
	inc_rt_migration(rt_se, rt_rq);
	inc_rt_group(rt_se, rt_rq);
}

static inline
void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
	WARN_ON(!rt_prio(rt_se_prio(rt_se)));
	WARN_ON(!rt_rq->rt_nr_running);
	rt_rq->rt_nr_running--;

	dec_rt_prio(rt_rq, rt_se_prio(rt_se));
	dec_rt_migration(rt_se, rt_rq);
	dec_rt_group(rt_se, rt_rq);
1044 1045
}

1046
static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
I
Ingo Molnar 已提交
1047
{
P
Peter Zijlstra 已提交
1048 1049 1050
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
	struct rt_prio_array *array = &rt_rq->active;
	struct rt_rq *group_rq = group_rt_rq(rt_se);
1051
	struct list_head *queue = array->queue + rt_se_prio(rt_se);
I
Ingo Molnar 已提交
1052

1053 1054 1055 1056 1057 1058 1059
	/*
	 * Don't enqueue the group if its throttled, or when empty.
	 * The latter is a consequence of the former when a child group
	 * get throttled and the current group doesn't have any other
	 * active members.
	 */
	if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
P
Peter Zijlstra 已提交
1060
		return;
1061

1062 1063 1064 1065
	if (head)
		list_add(&rt_se->run_list, queue);
	else
		list_add_tail(&rt_se->run_list, queue);
P
Peter Zijlstra 已提交
1066
	__set_bit(rt_se_prio(rt_se), array->bitmap);
1067

P
Peter Zijlstra 已提交
1068 1069 1070
	inc_rt_tasks(rt_se, rt_rq);
}

1071
static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
P
Peter Zijlstra 已提交
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
{
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
	struct rt_prio_array *array = &rt_rq->active;

	list_del_init(&rt_se->run_list);
	if (list_empty(array->queue + rt_se_prio(rt_se)))
		__clear_bit(rt_se_prio(rt_se), array->bitmap);

	dec_rt_tasks(rt_se, rt_rq);
}

/*
 * Because the prio of an upper entry depends on the lower
 * entries, we must remove entries top - down.
 */
1087
static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
P
Peter Zijlstra 已提交
1088
{
1089
	struct sched_rt_entity *back = NULL;
P
Peter Zijlstra 已提交
1090

1091 1092 1093 1094 1095 1096 1097
	for_each_sched_rt_entity(rt_se) {
		rt_se->back = back;
		back = rt_se;
	}

	for (rt_se = back; rt_se; rt_se = rt_se->back) {
		if (on_rt_rq(rt_se))
1098 1099 1100 1101
			__dequeue_rt_entity(rt_se);
	}
}

1102
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
1103 1104 1105
{
	dequeue_rt_stack(rt_se);
	for_each_sched_rt_entity(rt_se)
1106
		__enqueue_rt_entity(rt_se, head);
1107 1108 1109 1110 1111 1112 1113 1114 1115 1116
}

static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
	dequeue_rt_stack(rt_se);

	for_each_sched_rt_entity(rt_se) {
		struct rt_rq *rt_rq = group_rt_rq(rt_se);

		if (rt_rq && rt_rq->rt_nr_running)
1117
			__enqueue_rt_entity(rt_se, false);
1118
	}
I
Ingo Molnar 已提交
1119 1120 1121 1122 1123
}

/*
 * Adding/removing a task to/from a priority array:
 */
1124
static void
1125
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
P
Peter Zijlstra 已提交
1126 1127 1128
{
	struct sched_rt_entity *rt_se = &p->rt;

1129
	if (flags & ENQUEUE_WAKEUP)
P
Peter Zijlstra 已提交
1130 1131
		rt_se->timeout = 0;

1132
	enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
1133

1134
	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
1135
		enqueue_pushable_task(rq, p);
1136 1137

	inc_nr_running(rq);
P
Peter Zijlstra 已提交
1138 1139
}

1140
static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1141
{
P
Peter Zijlstra 已提交
1142
	struct sched_rt_entity *rt_se = &p->rt;
I
Ingo Molnar 已提交
1143

1144
	update_curr_rt(rq);
1145
	dequeue_rt_entity(rt_se);
1146

1147
	dequeue_pushable_task(rq, p);
1148 1149

	dec_nr_running(rq);
I
Ingo Molnar 已提交
1150 1151 1152
}

/*
1153 1154
 * Put task to the head or the end of the run list without the overhead of
 * dequeue followed by enqueue.
I
Ingo Molnar 已提交
1155
 */
1156 1157
static void
requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
P
Peter Zijlstra 已提交
1158
{
1159
	if (on_rt_rq(rt_se)) {
1160 1161 1162 1163 1164 1165 1166
		struct rt_prio_array *array = &rt_rq->active;
		struct list_head *queue = array->queue + rt_se_prio(rt_se);

		if (head)
			list_move(&rt_se->run_list, queue);
		else
			list_move_tail(&rt_se->run_list, queue);
1167
	}
P
Peter Zijlstra 已提交
1168 1169
}

1170
static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
I
Ingo Molnar 已提交
1171
{
P
Peter Zijlstra 已提交
1172 1173
	struct sched_rt_entity *rt_se = &p->rt;
	struct rt_rq *rt_rq;
I
Ingo Molnar 已提交
1174

P
Peter Zijlstra 已提交
1175 1176
	for_each_sched_rt_entity(rt_se) {
		rt_rq = rt_rq_of_se(rt_se);
1177
		requeue_rt_entity(rt_rq, rt_se, head);
P
Peter Zijlstra 已提交
1178
	}
I
Ingo Molnar 已提交
1179 1180
}

P
Peter Zijlstra 已提交
1181
static void yield_task_rt(struct rq *rq)
I
Ingo Molnar 已提交
1182
{
1183
	requeue_task_rt(rq, rq->curr, 0);
I
Ingo Molnar 已提交
1184 1185
}

1186
#ifdef CONFIG_SMP
1187 1188
static int find_lowest_rq(struct task_struct *task);

1189
static int
1190
select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
1191
{
1192 1193
	struct task_struct *curr;
	struct rq *rq;
1194

1195
	if (p->nr_cpus_allowed == 1)
1196 1197
		goto out;

1198 1199 1200 1201
	/* For anything but wake ups, just return the task_cpu */
	if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK)
		goto out;

1202 1203 1204 1205 1206
	rq = cpu_rq(cpu);

	rcu_read_lock();
	curr = ACCESS_ONCE(rq->curr); /* unlocked access */

1207
	/*
1208
	 * If the current task on @p's runqueue is an RT task, then
1209 1210 1211 1212
	 * try to see if we can wake this RT task up on another
	 * runqueue. Otherwise simply start this RT task
	 * on its current runqueue.
	 *
1213 1214 1215 1216 1217 1218 1219 1220 1221
	 * We want to avoid overloading runqueues. If the woken
	 * task is a higher priority, then it will stay on this CPU
	 * and the lower prio task should be moved to another CPU.
	 * Even though this will probably make the lower prio task
	 * lose its cache, we do not want to bounce a higher task
	 * around just because it gave up its CPU, perhaps for a
	 * lock?
	 *
	 * For equal prio tasks, we just let the scheduler sort it out.
1222 1223 1224 1225 1226 1227
	 *
	 * Otherwise, just let it ride on the affined RQ and the
	 * post-schedule router will push the preempted task away
	 *
	 * This test is optimistic, if we get it wrong the load-balancer
	 * will have to sort it out.
1228
	 */
1229
	if (curr && unlikely(rt_task(curr)) &&
1230
	    (curr->nr_cpus_allowed < 2 ||
1231
	     curr->prio <= p->prio)) {
1232
		int target = find_lowest_rq(p);
1233

1234 1235
		if (target != -1)
			cpu = target;
1236
	}
1237
	rcu_read_unlock();
1238

1239
out:
1240
	return cpu;
1241
}
1242 1243 1244

static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
{
1245
	if (rq->curr->nr_cpus_allowed == 1)
1246 1247
		return;

1248
	if (p->nr_cpus_allowed != 1
1249 1250
	    && cpupri_find(&rq->rd->cpupri, p, NULL))
		return;
1251

1252 1253
	if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
		return;
1254 1255 1256 1257 1258 1259 1260 1261 1262 1263

	/*
	 * There appears to be other cpus that can accept
	 * current and none to run 'p', so lets reschedule
	 * to try and push current away:
	 */
	requeue_task_rt(rq, p, 1);
	resched_task(rq->curr);
}

1264 1265
#endif /* CONFIG_SMP */

I
Ingo Molnar 已提交
1266 1267 1268
/*
 * Preempt the current task with a newly woken task if needed:
 */
P
Peter Zijlstra 已提交
1269
static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1270
{
1271
	if (p->prio < rq->curr->prio) {
I
Ingo Molnar 已提交
1272
		resched_task(rq->curr);
1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288
		return;
	}

#ifdef CONFIG_SMP
	/*
	 * If:
	 *
	 * - the newly woken task is of equal priority to the current task
	 * - the newly woken task is non-migratable while current is migratable
	 * - current will be preempted on the next reschedule
	 *
	 * we should check to see if current can readily move to a different
	 * cpu.  If so, we will reschedule to allow the push logic to try
	 * to move current somewhere else, making room for our non-migratable
	 * task.
	 */
1289
	if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
1290
		check_preempt_equal_prio(rq, p);
1291
#endif
I
Ingo Molnar 已提交
1292 1293
}

P
Peter Zijlstra 已提交
1294 1295
static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
						   struct rt_rq *rt_rq)
I
Ingo Molnar 已提交
1296
{
P
Peter Zijlstra 已提交
1297 1298
	struct rt_prio_array *array = &rt_rq->active;
	struct sched_rt_entity *next = NULL;
I
Ingo Molnar 已提交
1299 1300 1301 1302
	struct list_head *queue;
	int idx;

	idx = sched_find_first_bit(array->bitmap);
P
Peter Zijlstra 已提交
1303
	BUG_ON(idx >= MAX_RT_PRIO);
I
Ingo Molnar 已提交
1304 1305

	queue = array->queue + idx;
P
Peter Zijlstra 已提交
1306
	next = list_entry(queue->next, struct sched_rt_entity, run_list);
1307

P
Peter Zijlstra 已提交
1308 1309
	return next;
}
I
Ingo Molnar 已提交
1310

1311
static struct task_struct *_pick_next_task_rt(struct rq *rq)
P
Peter Zijlstra 已提交
1312 1313 1314
{
	struct sched_rt_entity *rt_se;
	struct task_struct *p;
1315
	struct rt_rq *rt_rq  = &rq->rt;
P
Peter Zijlstra 已提交
1316 1317 1318

	do {
		rt_se = pick_next_rt_entity(rq, rt_rq);
1319
		BUG_ON(!rt_se);
P
Peter Zijlstra 已提交
1320 1321 1322 1323
		rt_rq = group_rt_rq(rt_se);
	} while (rt_rq);

	p = rt_task_of(rt_se);
1324
	p->se.exec_start = rq_clock_task(rq);
1325 1326 1327 1328

	return p;
}

1329 1330
static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev)
1331
{
1332 1333 1334
	struct task_struct *p;
	struct rt_rq *rt_rq = &rq->rt;

1335 1336 1337 1338 1339 1340
#ifdef CONFIG_SMP
	/* Try to pull RT tasks here if we lower this rq's prio */
	if (rq->rt.highest_prio.curr > prev->prio)
		pull_rt_task(rq);
#endif

1341 1342 1343 1344 1345 1346
	if (!rt_rq->rt_nr_running)
		return NULL;

	if (rt_rq_throttled(rt_rq))
		return NULL;

1347
	put_prev_task(rq, prev);
1348 1349

	p = _pick_next_task_rt(rq);
1350 1351 1352 1353 1354

	/* The running task is never eligible for pushing */
	if (p)
		dequeue_pushable_task(rq, p);

1355
#ifdef CONFIG_SMP
1356 1357 1358 1359 1360
	/*
	 * We detect this state here so that we can avoid taking the RQ
	 * lock again later if there is no need to push
	 */
	rq->post_schedule = has_pushable_tasks(rq);
1361
#endif
1362

P
Peter Zijlstra 已提交
1363
	return p;
I
Ingo Molnar 已提交
1364 1365
}

1366
static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
I
Ingo Molnar 已提交
1367
{
1368
	update_curr_rt(rq);
1369 1370 1371 1372 1373

	/*
	 * The previous task needs to be made eligible for pushing
	 * if it is still active
	 */
1374
	if (on_rt_rq(&p->rt) && p->nr_cpus_allowed > 1)
1375
		enqueue_pushable_task(rq, p);
I
Ingo Molnar 已提交
1376 1377
}

1378
#ifdef CONFIG_SMP
P
Peter Zijlstra 已提交
1379

S
Steven Rostedt 已提交
1380 1381 1382
/* Only try algorithms three times */
#define RT_MAX_TRIES 3

1383 1384 1385
static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
{
	if (!task_running(rq, p) &&
1386
	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1387 1388 1389 1390
		return 1;
	return 0;
}

1391 1392 1393 1394 1395
/*
 * Return the highest pushable rq's task, which is suitable to be executed
 * on the cpu, NULL otherwise
 */
static struct task_struct *pick_highest_pushable_task(struct rq *rq, int cpu)
S
Steven Rostedt 已提交
1396
{
1397 1398
	struct plist_head *head = &rq->rt.pushable_tasks;
	struct task_struct *p;
1399

1400 1401
	if (!has_pushable_tasks(rq))
		return NULL;
1402

1403 1404 1405
	plist_for_each_entry(p, head, pushable_tasks) {
		if (pick_rt_task(rq, p, cpu))
			return p;
1406 1407
	}

1408
	return NULL;
S
Steven Rostedt 已提交
1409 1410
}

1411
static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
S
Steven Rostedt 已提交
1412

G
Gregory Haskins 已提交
1413 1414 1415
static int find_lowest_rq(struct task_struct *task)
{
	struct sched_domain *sd;
1416
	struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
G
Gregory Haskins 已提交
1417 1418
	int this_cpu = smp_processor_id();
	int cpu      = task_cpu(task);
G
Gregory Haskins 已提交
1419

1420 1421 1422 1423
	/* Make sure the mask is initialized first */
	if (unlikely(!lowest_mask))
		return -1;

1424
	if (task->nr_cpus_allowed == 1)
1425
		return -1; /* No other targets possible */
G
Gregory Haskins 已提交
1426

1427 1428
	if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
		return -1; /* No targets found */
G
Gregory Haskins 已提交
1429 1430 1431 1432 1433 1434 1435 1436 1437

	/*
	 * At this point we have built a mask of cpus representing the
	 * lowest priority tasks in the system.  Now we want to elect
	 * the best one based on our affinity and topology.
	 *
	 * We prioritize the last cpu that the task executed on since
	 * it is most likely cache-hot in that location.
	 */
1438
	if (cpumask_test_cpu(cpu, lowest_mask))
G
Gregory Haskins 已提交
1439 1440 1441 1442 1443 1444
		return cpu;

	/*
	 * Otherwise, we consult the sched_domains span maps to figure
	 * out which cpu is logically closest to our hot cache data.
	 */
R
Rusty Russell 已提交
1445 1446
	if (!cpumask_test_cpu(this_cpu, lowest_mask))
		this_cpu = -1; /* Skip this_cpu opt if not among lowest */
G
Gregory Haskins 已提交
1447

1448
	rcu_read_lock();
R
Rusty Russell 已提交
1449 1450 1451
	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_AFFINE) {
			int best_cpu;
G
Gregory Haskins 已提交
1452

R
Rusty Russell 已提交
1453 1454 1455 1456 1457
			/*
			 * "this_cpu" is cheaper to preempt than a
			 * remote processor.
			 */
			if (this_cpu != -1 &&
1458 1459
			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1460
				return this_cpu;
1461
			}
R
Rusty Russell 已提交
1462 1463 1464

			best_cpu = cpumask_first_and(lowest_mask,
						     sched_domain_span(sd));
1465 1466
			if (best_cpu < nr_cpu_ids) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1467
				return best_cpu;
1468
			}
G
Gregory Haskins 已提交
1469 1470
		}
	}
1471
	rcu_read_unlock();
G
Gregory Haskins 已提交
1472 1473 1474 1475 1476 1477

	/*
	 * And finally, if there were no matches within the domains
	 * just give the caller *something* to work with from the compatible
	 * locations.
	 */
R
Rusty Russell 已提交
1478 1479 1480 1481 1482 1483 1484
	if (this_cpu != -1)
		return this_cpu;

	cpu = cpumask_any(lowest_mask);
	if (cpu < nr_cpu_ids)
		return cpu;
	return -1;
1485 1486 1487
}

/* Will lock the rq it finds */
1488
static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
1489 1490 1491
{
	struct rq *lowest_rq = NULL;
	int tries;
1492
	int cpu;
S
Steven Rostedt 已提交
1493

1494 1495 1496
	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
		cpu = find_lowest_rq(task);

1497
		if ((cpu == -1) || (cpu == rq->cpu))
S
Steven Rostedt 已提交
1498 1499
			break;

1500 1501
		lowest_rq = cpu_rq(cpu);

S
Steven Rostedt 已提交
1502
		/* if the prio of this runqueue changed, try again */
1503
		if (double_lock_balance(rq, lowest_rq)) {
S
Steven Rostedt 已提交
1504 1505 1506 1507 1508 1509
			/*
			 * We had to unlock the run queue. In
			 * the mean time, task could have
			 * migrated already or had its affinity changed.
			 * Also make sure that it wasn't scheduled on its rq.
			 */
1510
			if (unlikely(task_rq(task) != rq ||
1511
				     !cpumask_test_cpu(lowest_rq->cpu,
1512
						       tsk_cpus_allowed(task)) ||
1513
				     task_running(rq, task) ||
P
Peter Zijlstra 已提交
1514
				     !task->on_rq)) {
1515

1516
				double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1517 1518 1519 1520 1521 1522
				lowest_rq = NULL;
				break;
			}
		}

		/* If this rq is still suitable use it. */
1523
		if (lowest_rq->rt.highest_prio.curr > task->prio)
S
Steven Rostedt 已提交
1524 1525 1526
			break;

		/* try again */
1527
		double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1528 1529 1530 1531 1532 1533
		lowest_rq = NULL;
	}

	return lowest_rq;
}

1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545
static struct task_struct *pick_next_pushable_task(struct rq *rq)
{
	struct task_struct *p;

	if (!has_pushable_tasks(rq))
		return NULL;

	p = plist_first_entry(&rq->rt.pushable_tasks,
			      struct task_struct, pushable_tasks);

	BUG_ON(rq->cpu != task_cpu(p));
	BUG_ON(task_current(rq, p));
1546
	BUG_ON(p->nr_cpus_allowed <= 1);
1547

P
Peter Zijlstra 已提交
1548
	BUG_ON(!p->on_rq);
1549 1550 1551 1552 1553
	BUG_ON(!rt_task(p));

	return p;
}

S
Steven Rostedt 已提交
1554 1555 1556 1557 1558
/*
 * If the current CPU has more than one RT task, see if the non
 * running task can migrate over to a CPU that is running a task
 * of lesser priority.
 */
1559
static int push_rt_task(struct rq *rq)
S
Steven Rostedt 已提交
1560 1561 1562
{
	struct task_struct *next_task;
	struct rq *lowest_rq;
1563
	int ret = 0;
S
Steven Rostedt 已提交
1564

G
Gregory Haskins 已提交
1565 1566 1567
	if (!rq->rt.overloaded)
		return 0;

1568
	next_task = pick_next_pushable_task(rq);
S
Steven Rostedt 已提交
1569 1570 1571
	if (!next_task)
		return 0;

P
Peter Zijlstra 已提交
1572
retry:
1573
	if (unlikely(next_task == rq->curr)) {
1574
		WARN_ON(1);
S
Steven Rostedt 已提交
1575
		return 0;
1576
	}
S
Steven Rostedt 已提交
1577 1578 1579 1580 1581 1582

	/*
	 * It's possible that the next_task slipped in of
	 * higher priority than current. If that's the case
	 * just reschedule current.
	 */
1583 1584
	if (unlikely(next_task->prio < rq->curr->prio)) {
		resched_task(rq->curr);
S
Steven Rostedt 已提交
1585 1586 1587
		return 0;
	}

1588
	/* We might release rq lock */
S
Steven Rostedt 已提交
1589 1590 1591
	get_task_struct(next_task);

	/* find_lock_lowest_rq locks the rq if found */
1592
	lowest_rq = find_lock_lowest_rq(next_task, rq);
S
Steven Rostedt 已提交
1593 1594 1595
	if (!lowest_rq) {
		struct task_struct *task;
		/*
1596
		 * find_lock_lowest_rq releases rq->lock
1597 1598 1599 1600 1601
		 * so it is possible that next_task has migrated.
		 *
		 * We need to make sure that the task is still on the same
		 * run-queue and is also still the next task eligible for
		 * pushing.
S
Steven Rostedt 已提交
1602
		 */
1603
		task = pick_next_pushable_task(rq);
1604 1605
		if (task_cpu(next_task) == rq->cpu && task == next_task) {
			/*
1606 1607 1608 1609
			 * The task hasn't migrated, and is still the next
			 * eligible task, but we failed to find a run-queue
			 * to push it to.  Do not retry in this case, since
			 * other cpus will pull from us when ready.
1610 1611
			 */
			goto out;
S
Steven Rostedt 已提交
1612
		}
1613

1614 1615 1616 1617
		if (!task)
			/* No more tasks, just exit */
			goto out;

1618
		/*
1619
		 * Something has shifted, try again.
1620
		 */
1621 1622 1623
		put_task_struct(next_task);
		next_task = task;
		goto retry;
S
Steven Rostedt 已提交
1624 1625
	}

1626
	deactivate_task(rq, next_task, 0);
S
Steven Rostedt 已提交
1627 1628
	set_task_cpu(next_task, lowest_rq->cpu);
	activate_task(lowest_rq, next_task, 0);
1629
	ret = 1;
S
Steven Rostedt 已提交
1630 1631 1632

	resched_task(lowest_rq->curr);

1633
	double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1634 1635 1636 1637

out:
	put_task_struct(next_task);

1638
	return ret;
S
Steven Rostedt 已提交
1639 1640 1641 1642 1643 1644 1645 1646 1647
}

static void push_rt_tasks(struct rq *rq)
{
	/* push_rt_task will return true if it moved an RT */
	while (push_rt_task(rq))
		;
}

1648 1649
static int pull_rt_task(struct rq *this_rq)
{
I
Ingo Molnar 已提交
1650
	int this_cpu = this_rq->cpu, ret = 0, cpu;
1651
	struct task_struct *p;
1652 1653
	struct rq *src_rq;

1654
	if (likely(!rt_overloaded(this_rq)))
1655 1656
		return 0;

P
Peter Zijlstra 已提交
1657 1658 1659 1660 1661 1662
	/*
	 * Match the barrier from rt_set_overloaded; this guarantees that if we
	 * see overloaded we must also see the rto_mask bit.
	 */
	smp_rmb();

1663
	for_each_cpu(cpu, this_rq->rd->rto_mask) {
1664 1665 1666 1667
		if (this_cpu == cpu)
			continue;

		src_rq = cpu_rq(cpu);
1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679

		/*
		 * Don't bother taking the src_rq->lock if the next highest
		 * task is known to be lower-priority than our current task.
		 * This may look racy, but if this value is about to go
		 * logically higher, the src_rq will push this task away.
		 * And if its going logically lower, we do not care
		 */
		if (src_rq->rt.highest_prio.next >=
		    this_rq->rt.highest_prio.curr)
			continue;

1680 1681 1682
		/*
		 * We can potentially drop this_rq's lock in
		 * double_lock_balance, and another CPU could
1683
		 * alter this_rq
1684
		 */
1685
		double_lock_balance(this_rq, src_rq);
1686 1687

		/*
1688 1689
		 * We can pull only a task, which is pushable
		 * on its rq, and no others.
1690
		 */
1691
		p = pick_highest_pushable_task(src_rq, this_cpu);
1692 1693 1694 1695 1696

		/*
		 * Do we have an RT task that preempts
		 * the to-be-scheduled task?
		 */
1697
		if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
1698
			WARN_ON(p == src_rq->curr);
P
Peter Zijlstra 已提交
1699
			WARN_ON(!p->on_rq);
1700 1701 1702 1703 1704 1705 1706

			/*
			 * There's a chance that p is higher in priority
			 * than what's currently running on its cpu.
			 * This is just that p is wakeing up and hasn't
			 * had a chance to schedule. We only pull
			 * p if it is lower in priority than the
1707
			 * current task on the run queue
1708
			 */
1709
			if (p->prio < src_rq->curr->prio)
M
Mike Galbraith 已提交
1710
				goto skip;
1711 1712 1713 1714 1715 1716 1717 1718 1719

			ret = 1;

			deactivate_task(src_rq, p, 0);
			set_task_cpu(p, this_cpu);
			activate_task(this_rq, p, 0);
			/*
			 * We continue with the search, just in
			 * case there's an even higher prio task
L
Lucas De Marchi 已提交
1720
			 * in another runqueue. (low likelihood
1721 1722 1723
			 * but possible)
			 */
		}
P
Peter Zijlstra 已提交
1724
skip:
1725
		double_unlock_balance(this_rq, src_rq);
1726 1727 1728 1729 1730
	}

	return ret;
}

1731
static void post_schedule_rt(struct rq *rq)
S
Steven Rostedt 已提交
1732
{
1733
	push_rt_tasks(rq);
S
Steven Rostedt 已提交
1734 1735
}

1736 1737 1738 1739
/*
 * If we are not running and we are not going to reschedule soon, we should
 * try to push tasks away now
 */
1740
static void task_woken_rt(struct rq *rq, struct task_struct *p)
1741
{
1742
	if (!task_running(rq, p) &&
1743
	    !test_tsk_need_resched(rq->curr) &&
1744
	    has_pushable_tasks(rq) &&
1745
	    p->nr_cpus_allowed > 1 &&
1746
	    (dl_task(rq->curr) || rt_task(rq->curr)) &&
1747
	    (rq->curr->nr_cpus_allowed < 2 ||
1748
	     rq->curr->prio <= p->prio))
1749 1750 1751
		push_rt_tasks(rq);
}

1752
static void set_cpus_allowed_rt(struct task_struct *p,
1753
				const struct cpumask *new_mask)
1754
{
1755 1756
	struct rq *rq;
	int weight;
1757 1758 1759

	BUG_ON(!rt_task(p));

1760 1761
	if (!p->on_rq)
		return;
1762

1763
	weight = cpumask_weight(new_mask);
1764

1765 1766 1767 1768
	/*
	 * Only update if the process changes its state from whether it
	 * can migrate or not.
	 */
1769
	if ((p->nr_cpus_allowed > 1) == (weight > 1))
1770
		return;
1771

1772
	rq = task_rq(p);
1773

1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785
	/*
	 * The process used to be able to migrate OR it can now migrate
	 */
	if (weight <= 1) {
		if (!task_current(rq, p))
			dequeue_pushable_task(rq, p);
		BUG_ON(!rq->rt.rt_nr_migratory);
		rq->rt.rt_nr_migratory--;
	} else {
		if (!task_current(rq, p))
			enqueue_pushable_task(rq, p);
		rq->rt.rt_nr_migratory++;
1786
	}
1787 1788

	update_rt_migration(&rq->rt);
1789
}
1790

1791
/* Assumes rq->lock is held */
1792
static void rq_online_rt(struct rq *rq)
1793 1794 1795
{
	if (rq->rt.overloaded)
		rt_set_overload(rq);
1796

P
Peter Zijlstra 已提交
1797 1798
	__enable_runtime(rq);

1799
	cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
1800 1801 1802
}

/* Assumes rq->lock is held */
1803
static void rq_offline_rt(struct rq *rq)
1804 1805 1806
{
	if (rq->rt.overloaded)
		rt_clear_overload(rq);
1807

P
Peter Zijlstra 已提交
1808 1809
	__disable_runtime(rq);

1810
	cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
1811
}
1812 1813 1814 1815 1816

/*
 * When switch from the rt queue, we bring ourselves to a position
 * that we might want to pull RT tasks from other runqueues.
 */
P
Peter Zijlstra 已提交
1817
static void switched_from_rt(struct rq *rq, struct task_struct *p)
1818 1819 1820 1821 1822 1823 1824 1825
{
	/*
	 * If there are other RT tasks then we will reschedule
	 * and the scheduling of the other RT tasks will handle
	 * the balancing. But if we are the last RT task
	 * we may need to handle the pulling of RT tasks
	 * now.
	 */
1826 1827 1828 1829 1830
	if (!p->on_rq || rq->rt.rt_nr_running)
		return;

	if (pull_rt_task(rq))
		resched_task(rq->curr);
1831
}
1832

1833
void init_sched_rt_class(void)
1834 1835 1836
{
	unsigned int i;

1837
	for_each_possible_cpu(i) {
1838
		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
1839
					GFP_KERNEL, cpu_to_node(i));
1840
	}
1841
}
1842 1843 1844 1845 1846 1847 1848
#endif /* CONFIG_SMP */

/*
 * When switching a task to RT, we may overload the runqueue
 * with RT tasks. In this case we try to push them off to
 * other runqueues.
 */
P
Peter Zijlstra 已提交
1849
static void switched_to_rt(struct rq *rq, struct task_struct *p)
1850 1851 1852 1853 1854 1855 1856 1857 1858 1859
{
	int check_resched = 1;

	/*
	 * If we are already running, then there's nothing
	 * that needs to be done. But if we are not running
	 * we may need to preempt the current running task.
	 * If that current running task is also an RT task
	 * then see if we can move to another run queue.
	 */
P
Peter Zijlstra 已提交
1860
	if (p->on_rq && rq->curr != p) {
1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875
#ifdef CONFIG_SMP
		if (rq->rt.overloaded && push_rt_task(rq) &&
		    /* Don't resched if we changed runqueues */
		    rq != task_rq(p))
			check_resched = 0;
#endif /* CONFIG_SMP */
		if (check_resched && p->prio < rq->curr->prio)
			resched_task(rq->curr);
	}
}

/*
 * Priority of the task has changed. This may cause
 * us to initiate a push or pull.
 */
P
Peter Zijlstra 已提交
1876 1877
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
1878
{
P
Peter Zijlstra 已提交
1879
	if (!p->on_rq)
P
Peter Zijlstra 已提交
1880 1881 1882
		return;

	if (rq->curr == p) {
1883 1884 1885 1886 1887 1888 1889 1890 1891
#ifdef CONFIG_SMP
		/*
		 * If our priority decreases while running, we
		 * may need to pull tasks to this runqueue.
		 */
		if (oldprio < p->prio)
			pull_rt_task(rq);
		/*
		 * If there's a higher priority task waiting to run
1892 1893 1894
		 * then reschedule. Note, the above pull_rt_task
		 * can release the rq lock and p could migrate.
		 * Only reschedule if p is still on the same runqueue.
1895
		 */
1896
		if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
1897 1898 1899 1900 1901
			resched_task(p);
#else
		/* For UP simply resched on drop of prio */
		if (oldprio < p->prio)
			resched_task(p);
S
Steven Rostedt 已提交
1902
#endif /* CONFIG_SMP */
1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913
	} else {
		/*
		 * This task is not running, but if it is
		 * greater than the current running task
		 * then reschedule.
		 */
		if (p->prio < rq->curr->prio)
			resched_task(rq->curr);
	}
}

1914 1915 1916 1917
static void watchdog(struct rq *rq, struct task_struct *p)
{
	unsigned long soft, hard;

1918 1919 1920
	/* max may change after cur was read, this will be fixed next tick */
	soft = task_rlimit(p, RLIMIT_RTTIME);
	hard = task_rlimit_max(p, RLIMIT_RTTIME);
1921 1922 1923 1924

	if (soft != RLIM_INFINITY) {
		unsigned long next;

1925 1926 1927 1928 1929
		if (p->rt.watchdog_stamp != jiffies) {
			p->rt.timeout++;
			p->rt.watchdog_stamp = jiffies;
		}

1930
		next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1931
		if (p->rt.timeout > next)
1932
			p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
1933 1934
	}
}
I
Ingo Molnar 已提交
1935

P
Peter Zijlstra 已提交
1936
static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
I
Ingo Molnar 已提交
1937
{
1938 1939
	struct sched_rt_entity *rt_se = &p->rt;

1940 1941
	update_curr_rt(rq);

1942 1943
	watchdog(rq, p);

I
Ingo Molnar 已提交
1944 1945 1946 1947 1948 1949 1950
	/*
	 * RR tasks need a special form of timeslice management.
	 * FIFO tasks have no timeslices.
	 */
	if (p->policy != SCHED_RR)
		return;

P
Peter Zijlstra 已提交
1951
	if (--p->rt.time_slice)
I
Ingo Molnar 已提交
1952 1953
		return;

1954
	p->rt.time_slice = sched_rr_timeslice;
I
Ingo Molnar 已提交
1955

1956
	/*
L
Li Bin 已提交
1957 1958
	 * Requeue to the end of queue if we (and all of our ancestors) are not
	 * the only element on the queue
1959
	 */
1960 1961 1962 1963 1964 1965
	for_each_sched_rt_entity(rt_se) {
		if (rt_se->run_list.prev != rt_se->run_list.next) {
			requeue_task_rt(rq, p, 0);
			set_tsk_need_resched(p);
			return;
		}
1966
	}
I
Ingo Molnar 已提交
1967 1968
}

1969 1970 1971 1972
static void set_curr_task_rt(struct rq *rq)
{
	struct task_struct *p = rq->curr;

1973
	p->se.exec_start = rq_clock_task(rq);
1974 1975 1976

	/* The running task is never eligible for pushing */
	dequeue_pushable_task(rq, p);
1977 1978
}

1979
static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
1980 1981 1982 1983 1984
{
	/*
	 * Time slice is 0 for SCHED_FIFO tasks
	 */
	if (task->policy == SCHED_RR)
1985
		return sched_rr_timeslice;
1986 1987 1988 1989
	else
		return 0;
}

1990
const struct sched_class rt_sched_class = {
1991
	.next			= &fair_sched_class,
I
Ingo Molnar 已提交
1992 1993 1994 1995 1996 1997 1998 1999 2000
	.enqueue_task		= enqueue_task_rt,
	.dequeue_task		= dequeue_task_rt,
	.yield_task		= yield_task_rt,

	.check_preempt_curr	= check_preempt_curr_rt,

	.pick_next_task		= pick_next_task_rt,
	.put_prev_task		= put_prev_task_rt,

2001
#ifdef CONFIG_SMP
L
Li Zefan 已提交
2002 2003
	.select_task_rq		= select_task_rq_rt,

2004
	.set_cpus_allowed       = set_cpus_allowed_rt,
2005 2006
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
2007
	.post_schedule		= post_schedule_rt,
2008
	.task_woken		= task_woken_rt,
2009
	.switched_from		= switched_from_rt,
2010
#endif
I
Ingo Molnar 已提交
2011

2012
	.set_curr_task          = set_curr_task_rt,
I
Ingo Molnar 已提交
2013
	.task_tick		= task_tick_rt,
2014

2015 2016
	.get_rr_interval	= get_rr_interval_rt,

2017 2018
	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,
I
Ingo Molnar 已提交
2019
};
2020 2021 2022 2023

#ifdef CONFIG_SCHED_DEBUG
extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);

2024
void print_rt_stats(struct seq_file *m, int cpu)
2025
{
C
Cheng Xu 已提交
2026
	rt_rq_iter_t iter;
2027 2028 2029
	struct rt_rq *rt_rq;

	rcu_read_lock();
C
Cheng Xu 已提交
2030
	for_each_rt_rq(rt_rq, iter, cpu_rq(cpu))
2031 2032 2033
		print_rt_rq(m, cpu, rt_rq);
	rcu_read_unlock();
}
2034
#endif /* CONFIG_SCHED_DEBUG */