rt.c 53.1 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
#include "sched.h"

#include <linux/slab.h>
9
#include <linux/irq_work.h>
10

11 12
int sched_rr_timeslice = RR_TIMESLICE;

13 14 15 16 17 18 19 20 21
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);
	int idle = 0;
P
Peter Zijlstra 已提交
22
	int overrun;
23

P
Peter Zijlstra 已提交
24
	raw_spin_lock(&rt_b->rt_runtime_lock);
25
	for (;;) {
P
Peter Zijlstra 已提交
26
		overrun = hrtimer_forward_now(timer, rt_b->rt_period);
27 28 29
		if (!overrun)
			break;

P
Peter Zijlstra 已提交
30
		raw_spin_unlock(&rt_b->rt_runtime_lock);
31
		idle = do_sched_rt_period_timer(rt_b, overrun);
P
Peter Zijlstra 已提交
32
		raw_spin_lock(&rt_b->rt_runtime_lock);
33
	}
P
Peter Zijlstra 已提交
34 35
	if (idle)
		rt_b->rt_period_active = 0;
P
Peter Zijlstra 已提交
36
	raw_spin_unlock(&rt_b->rt_runtime_lock);
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

	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;

	raw_spin_lock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
59 60 61 62 63
	if (!rt_b->rt_period_active) {
		rt_b->rt_period_active = 1;
		hrtimer_forward_now(&rt_b->rt_period_timer, rt_b->rt_period);
		hrtimer_start_expires(&rt_b->rt_period_timer, HRTIMER_MODE_ABS_PINNED);
	}
64 65 66
	raw_spin_unlock(&rt_b->rt_runtime_lock);
}

67 68 69 70
#ifdef CONFIG_SMP
static void push_irq_work_func(struct irq_work *work);
#endif

71
void init_rt_rq(struct rt_rq *rt_rq)
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
{
	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);
90 91 92 93 94 95

#ifdef HAVE_RT_PUSH_IPI
	rt_rq->push_flags = 0;
	rt_rq->push_cpu = nr_cpu_ids;
	raw_spin_lock_init(&rt_rq->push_lock);
	init_irq_work(&rt_rq->push_work, push_irq_work_func);
96
#endif
97
#endif /* CONFIG_SMP */
98 99
	/* We start is dequeued state, because no RT tasks are queued */
	rt_rq->rt_queued = 0;
100 101 102 103 104 105 106

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

107
#ifdef CONFIG_RT_GROUP_SCHED
108 109 110 111
static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
{
	hrtimer_cancel(&rt_b->rt_period_timer);
}
112 113 114

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

115 116
static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
{
117 118 119
#ifdef CONFIG_SCHED_DEBUG
	WARN_ON_ONCE(!rt_entity_is_task(rt_se));
#endif
120 121 122 123 124 125 126 127 128 129 130 131 132
	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;
}

133 134 135 136 137 138 139
static inline struct rq *rq_of_rt_se(struct sched_rt_entity *rt_se)
{
	struct rt_rq *rt_rq = rt_se->rt_rq;

	return rt_rq->rq;
}

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 200 201 202 203 204 205 206 207 208 209 210 211
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;

212
		init_rt_rq(rt_rq);
213 214 215 216 217 218 219 220 221 222 223 224
		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;
}

225 226
#else /* CONFIG_RT_GROUP_SCHED */

227 228
#define rt_entity_is_task(rt_se) (1)

229 230 231 232 233
static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se)
{
	return container_of(rt_se, struct task_struct, rt);
}

234 235 236 237 238
static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq)
{
	return container_of(rt_rq, struct rq, rt);
}

239
static inline struct rq *rq_of_rt_se(struct sched_rt_entity *rt_se)
240 241
{
	struct task_struct *p = rt_task_of(rt_se);
242 243 244 245 246 247 248

	return task_rq(p);
}

static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se)
{
	struct rq *rq = rq_of_rt_se(rt_se);
249 250 251 252

	return &rq->rt;
}

253 254 255 256 257 258
void free_rt_sched_group(struct task_group *tg) { }

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

S
Steven Rostedt 已提交
261
#ifdef CONFIG_SMP
I
Ingo Molnar 已提交
262

263 264
static int pull_rt_task(struct rq *this_rq);

P
Peter Zijlstra 已提交
265 266 267 268 269 270
static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev)
{
	/* Try to pull RT tasks here if we lower this rq's prio */
	return rq->rt.highest_prio.curr > prev->prio;
}

271
static inline int rt_overloaded(struct rq *rq)
S
Steven Rostedt 已提交
272
{
273
	return atomic_read(&rq->rd->rto_count);
S
Steven Rostedt 已提交
274
}
I
Ingo Molnar 已提交
275

S
Steven Rostedt 已提交
276 277
static inline void rt_set_overload(struct rq *rq)
{
278 279 280
	if (!rq->online)
		return;

281
	cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
S
Steven Rostedt 已提交
282 283 284 285 286 287
	/*
	 * 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 已提交
288 289
	 *
	 * Matched by the barrier in pull_rt_task().
S
Steven Rostedt 已提交
290
	 */
P
Peter Zijlstra 已提交
291
	smp_wmb();
292
	atomic_inc(&rq->rd->rto_count);
S
Steven Rostedt 已提交
293
}
I
Ingo Molnar 已提交
294

S
Steven Rostedt 已提交
295 296
static inline void rt_clear_overload(struct rq *rq)
{
297 298 299
	if (!rq->online)
		return;

S
Steven Rostedt 已提交
300
	/* the order here really doesn't matter */
301
	atomic_dec(&rq->rd->rto_count);
302
	cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
S
Steven Rostedt 已提交
303
}
304

305
static void update_rt_migration(struct rt_rq *rt_rq)
306
{
307
	if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) {
308 309 310
		if (!rt_rq->overloaded) {
			rt_set_overload(rq_of_rt_rq(rt_rq));
			rt_rq->overloaded = 1;
311
		}
312 313 314
	} else if (rt_rq->overloaded) {
		rt_clear_overload(rq_of_rt_rq(rt_rq));
		rt_rq->overloaded = 0;
315
	}
316
}
S
Steven Rostedt 已提交
317

318 319
static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
320 321
	struct task_struct *p;

322 323 324
	if (!rt_entity_is_task(rt_se))
		return;

325
	p = rt_task_of(rt_se);
326 327 328
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total++;
329
	if (p->nr_cpus_allowed > 1)
330 331 332 333 334 335 336
		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)
{
337 338
	struct task_struct *p;

339 340 341
	if (!rt_entity_is_task(rt_se))
		return;

342
	p = rt_task_of(rt_se);
343 344 345
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total--;
346
	if (p->nr_cpus_allowed > 1)
347 348 349 350 351
		rt_rq->rt_nr_migratory--;

	update_rt_migration(rt_rq);
}

352 353 354 355 356
static inline int has_pushable_tasks(struct rq *rq)
{
	return !plist_head_empty(&rq->rt.pushable_tasks);
}

P
Peter Zijlstra 已提交
357 358 359 360 361 362 363 364 365
static inline void set_post_schedule(struct rq *rq)
{
	/*
	 * 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);
}

366 367 368 369 370
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);
371 372 373 374

	/* Update the highest prio pushable task */
	if (p->prio < rq->rt.highest_prio.next)
		rq->rt.highest_prio.next = p->prio;
375 376 377 378 379 380
}

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

381 382 383 384 385 386 387
	/* 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;
388 389
}

390 391
#else

392
static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
P
Peter Zijlstra 已提交
393
{
P
Peter Zijlstra 已提交
394 395
}

396 397 398 399
static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
{
}

400
static inline
401 402 403 404
void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
}

405
static inline
406 407 408
void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
}
409

P
Peter Zijlstra 已提交
410 411 412 413 414 415 416 417 418 419 420 421 422
static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev)
{
	return false;
}

static inline int pull_rt_task(struct rq *this_rq)
{
	return 0;
}

static inline void set_post_schedule(struct rq *rq)
{
}
S
Steven Rostedt 已提交
423 424
#endif /* CONFIG_SMP */

425 426 427
static void enqueue_top_rt_rq(struct rt_rq *rt_rq);
static void dequeue_top_rt_rq(struct rt_rq *rt_rq);

P
Peter Zijlstra 已提交
428 429 430 431 432
static inline int on_rt_rq(struct sched_rt_entity *rt_se)
{
	return !list_empty(&rt_se->run_list);
}

433
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
434

P
Peter Zijlstra 已提交
435
static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
436 437
{
	if (!rt_rq->tg)
P
Peter Zijlstra 已提交
438
		return RUNTIME_INF;
P
Peter Zijlstra 已提交
439

P
Peter Zijlstra 已提交
440 441 442 443 444 445
	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 已提交
446 447
}

C
Cheng Xu 已提交
448 449
typedef struct task_group *rt_rq_iter_t;

450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
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 已提交
467

P
Peter Zijlstra 已提交
468 469 470 471 472 473 474 475
#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;
}

476
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
P
Peter Zijlstra 已提交
477 478
static void dequeue_rt_entity(struct sched_rt_entity *rt_se);

P
Peter Zijlstra 已提交
479
static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
480
{
481
	struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
482
	struct rq *rq = rq_of_rt_rq(rt_rq);
483 484
	struct sched_rt_entity *rt_se;

485
	int cpu = cpu_of(rq);
486 487

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

489
	if (rt_rq->rt_nr_running) {
490 491 492
		if (!rt_se)
			enqueue_top_rt_rq(rt_rq);
		else if (!on_rt_rq(rt_se))
493
			enqueue_rt_entity(rt_se, false);
494

495
		if (rt_rq->highest_prio.curr < curr->prio)
496
			resched_curr(rq);
P
Peter Zijlstra 已提交
497 498 499
	}
}

P
Peter Zijlstra 已提交
500
static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
501
{
502
	struct sched_rt_entity *rt_se;
503
	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
504

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

507 508 509
	if (!rt_se)
		dequeue_top_rt_rq(rt_rq);
	else if (on_rt_rq(rt_se))
P
Peter Zijlstra 已提交
510 511 512
		dequeue_rt_entity(rt_se);
}

513 514 515 516 517
static inline int rt_rq_throttled(struct rt_rq *rt_rq)
{
	return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted;
}

P
Peter Zijlstra 已提交
518 519 520 521 522 523 524 525 526 527 528 529
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;
}

530
#ifdef CONFIG_SMP
531
static inline const struct cpumask *sched_rt_period_mask(void)
532
{
N
Nathan Zimmer 已提交
533
	return this_rq()->rd->span;
534
}
P
Peter Zijlstra 已提交
535
#else
536
static inline const struct cpumask *sched_rt_period_mask(void)
537
{
538
	return cpu_online_mask;
539 540
}
#endif
P
Peter Zijlstra 已提交
541

542 543
static inline
struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
P
Peter Zijlstra 已提交
544
{
545 546
	return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
}
P
Peter Zijlstra 已提交
547

P
Peter Zijlstra 已提交
548 549 550 551 552
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &rt_rq->tg->rt_bandwidth;
}

553
#else /* !CONFIG_RT_GROUP_SCHED */
554 555 556

static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
{
P
Peter Zijlstra 已提交
557 558 559 560 561 562
	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 已提交
563 564
}

C
Cheng Xu 已提交
565 566 567 568 569
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 已提交
570 571 572 573 574 575 576 577
#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 已提交
578
static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
579
{
580 581 582 583 584 585
	struct rq *rq = rq_of_rt_rq(rt_rq);

	if (!rt_rq->rt_nr_running)
		return;

	enqueue_top_rt_rq(rt_rq);
586
	resched_curr(rq);
P
Peter Zijlstra 已提交
587 588
}

P
Peter Zijlstra 已提交
589
static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
590
{
591
	dequeue_top_rt_rq(rt_rq);
P
Peter Zijlstra 已提交
592 593
}

594 595 596 597 598
static inline int rt_rq_throttled(struct rt_rq *rt_rq)
{
	return rt_rq->rt_throttled;
}

599
static inline const struct cpumask *sched_rt_period_mask(void)
600
{
601
	return cpu_online_mask;
602 603 604 605 606 607 608 609
}

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 已提交
610 611 612 613 614
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &def_rt_bandwidth;
}

615
#endif /* CONFIG_RT_GROUP_SCHED */
616

617 618 619 620 621 622 623 624
bool sched_rt_bandwidth_account(struct rt_rq *rt_rq)
{
	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

	return (hrtimer_active(&rt_b->rt_period_timer) ||
		rt_rq->rt_time < rt_b->rt_runtime);
}

P
Peter Zijlstra 已提交
625
#ifdef CONFIG_SMP
626 627 628
/*
 * We ran out of runtime, see if we can borrow some from our neighbours.
 */
629
static int do_balance_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
630 631
{
	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
632
	struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd;
P
Peter Zijlstra 已提交
633 634 635
	int i, weight, more = 0;
	u64 rt_period;

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

638
	raw_spin_lock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
639
	rt_period = ktime_to_ns(rt_b->rt_period);
640
	for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
641 642 643 644 645 646
		struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
		s64 diff;

		if (iter == rt_rq)
			continue;

647
		raw_spin_lock(&iter->rt_runtime_lock);
648 649 650 651 652
		/*
		 * 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 已提交
653 654 655
		if (iter->rt_runtime == RUNTIME_INF)
			goto next;

656 657 658 659
		/*
		 * From runqueues with spare time, take 1/n part of their
		 * spare time, but no more than our period.
		 */
P
Peter Zijlstra 已提交
660 661
		diff = iter->rt_runtime - iter->rt_time;
		if (diff > 0) {
662
			diff = div_u64((u64)diff, weight);
P
Peter Zijlstra 已提交
663 664 665 666 667 668
			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) {
669
				raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
670 671 672
				break;
			}
		}
P
Peter Zijlstra 已提交
673
next:
674
		raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
675
	}
676
	raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
677 678 679

	return more;
}
P
Peter Zijlstra 已提交
680

681 682 683
/*
 * Ensure this RQ takes back all the runtime it lend to its neighbours.
 */
P
Peter Zijlstra 已提交
684 685 686
static void __disable_runtime(struct rq *rq)
{
	struct root_domain *rd = rq->rd;
C
Cheng Xu 已提交
687
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
688 689 690 691 692
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

C
Cheng Xu 已提交
693
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
694 695 696 697
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
		s64 want;
		int i;

698 699
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
700 701 702 703 704
		/*
		 * 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 已提交
705 706 707
		if (rt_rq->rt_runtime == RUNTIME_INF ||
				rt_rq->rt_runtime == rt_b->rt_runtime)
			goto balanced;
708
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
709

710 711 712 713 714
		/*
		 * 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 已提交
715 716
		want = rt_b->rt_runtime - rt_rq->rt_runtime;

717 718 719
		/*
		 * Greedy reclaim, take back as much as we can.
		 */
720
		for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
721 722 723
			struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
			s64 diff;

724 725 726
			/*
			 * Can't reclaim from ourselves or disabled runqueues.
			 */
727
			if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
P
Peter Zijlstra 已提交
728 729
				continue;

730
			raw_spin_lock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
731 732 733 734 735 736 737 738
			if (want > 0) {
				diff = min_t(s64, iter->rt_runtime, want);
				iter->rt_runtime -= diff;
				want -= diff;
			} else {
				iter->rt_runtime -= want;
				want -= want;
			}
739
			raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
740 741 742 743 744

			if (!want)
				break;
		}

745
		raw_spin_lock(&rt_rq->rt_runtime_lock);
746 747 748 749
		/*
		 * We cannot be left wanting - that would mean some runtime
		 * leaked out of the system.
		 */
P
Peter Zijlstra 已提交
750 751
		BUG_ON(want);
balanced:
752 753 754 755
		/*
		 * Disable all the borrow logic by pretending we have inf
		 * runtime - in which case borrowing doesn't make sense.
		 */
P
Peter Zijlstra 已提交
756
		rt_rq->rt_runtime = RUNTIME_INF;
757
		rt_rq->rt_throttled = 0;
758 759
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
760 761 762

		/* Make rt_rq available for pick_next_task() */
		sched_rt_rq_enqueue(rt_rq);
P
Peter Zijlstra 已提交
763 764 765 766 767
	}
}

static void __enable_runtime(struct rq *rq)
{
C
Cheng Xu 已提交
768
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
769 770 771 772 773
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

774 775 776
	/*
	 * Reset each runqueue's bandwidth settings
	 */
C
Cheng Xu 已提交
777
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
778 779
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

780 781
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
782 783
		rt_rq->rt_runtime = rt_b->rt_runtime;
		rt_rq->rt_time = 0;
784
		rt_rq->rt_throttled = 0;
785 786
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
787 788 789
	}
}

790 791 792 793
static int balance_runtime(struct rt_rq *rt_rq)
{
	int more = 0;

794 795 796
	if (!sched_feat(RT_RUNTIME_SHARE))
		return more;

797
	if (rt_rq->rt_time > rt_rq->rt_runtime) {
798
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
799
		more = do_balance_runtime(rt_rq);
800
		raw_spin_lock(&rt_rq->rt_runtime_lock);
801 802 803 804
	}

	return more;
}
805
#else /* !CONFIG_SMP */
806 807 808 809
static inline int balance_runtime(struct rt_rq *rt_rq)
{
	return 0;
}
810
#endif /* CONFIG_SMP */
P
Peter Zijlstra 已提交
811

812 813
static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
{
814
	int i, idle = 1, throttled = 0;
815
	const struct cpumask *span;
816 817

	span = sched_rt_period_mask();
818 819 820 821 822 823 824 825 826 827 828 829 830
#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
831
	for_each_cpu(i, span) {
832 833 834 835
		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);

836
		raw_spin_lock(&rq->lock);
837 838 839
		if (rt_rq->rt_time) {
			u64 runtime;

840
			raw_spin_lock(&rt_rq->rt_runtime_lock);
841 842 843 844 845 846 847
			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;
848 849

				/*
850 851 852 853 854
				 * When we're idle and a woken (rt) task is
				 * throttled check_preempt_curr() will set
				 * skip_update and the time between the wakeup
				 * and this unthrottle will get accounted as
				 * 'runtime'.
855 856
				 */
				if (rt_rq->rt_nr_running && rq->curr == rq->idle)
857
					rq_clock_skip_update(rq, false);
858 859 860
			}
			if (rt_rq->rt_time || rt_rq->rt_nr_running)
				idle = 0;
861
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
862
		} else if (rt_rq->rt_nr_running) {
863
			idle = 0;
864 865 866
			if (!rt_rq_throttled(rt_rq))
				enqueue = 1;
		}
867 868
		if (rt_rq->rt_throttled)
			throttled = 1;
869 870 871

		if (enqueue)
			sched_rt_rq_enqueue(rt_rq);
872
		raw_spin_unlock(&rq->lock);
873 874
	}

875 876 877
	if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
		return 1;

878 879
	return idle;
}
P
Peter Zijlstra 已提交
880

P
Peter Zijlstra 已提交
881 882
static inline int rt_se_prio(struct sched_rt_entity *rt_se)
{
883
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
884 885 886
	struct rt_rq *rt_rq = group_rt_rq(rt_se);

	if (rt_rq)
887
		return rt_rq->highest_prio.curr;
P
Peter Zijlstra 已提交
888 889 890 891 892
#endif

	return rt_task_of(rt_se)->prio;
}

P
Peter Zijlstra 已提交
893
static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
894
{
P
Peter Zijlstra 已提交
895
	u64 runtime = sched_rt_runtime(rt_rq);
P
Peter Zijlstra 已提交
896 897

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

900
	if (runtime >= sched_rt_period(rt_rq))
P
Peter Zijlstra 已提交
901 902
		return 0;

903 904 905 906
	balance_runtime(rt_rq);
	runtime = sched_rt_runtime(rt_rq);
	if (runtime == RUNTIME_INF)
		return 0;
P
Peter Zijlstra 已提交
907

P
Peter Zijlstra 已提交
908
	if (rt_rq->rt_time > runtime) {
909 910 911 912 913 914 915 916
		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)) {
			rt_rq->rt_throttled = 1;
J
John Stultz 已提交
917
			printk_deferred_once("sched: RT throttling activated\n");
918 919 920 921 922 923 924 925 926
		} 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 已提交
927
		if (rt_rq_throttled(rt_rq)) {
P
Peter Zijlstra 已提交
928
			sched_rt_rq_dequeue(rt_rq);
P
Peter Zijlstra 已提交
929 930
			return 1;
		}
P
Peter Zijlstra 已提交
931 932 933 934 935
	}

	return 0;
}

I
Ingo Molnar 已提交
936 937 938 939
/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
A
Alexey Dobriyan 已提交
940
static void update_curr_rt(struct rq *rq)
I
Ingo Molnar 已提交
941 942
{
	struct task_struct *curr = rq->curr;
P
Peter Zijlstra 已提交
943
	struct sched_rt_entity *rt_se = &curr->rt;
I
Ingo Molnar 已提交
944 945
	u64 delta_exec;

P
Peter Zijlstra 已提交
946
	if (curr->sched_class != &rt_sched_class)
I
Ingo Molnar 已提交
947 948
		return;

949
	delta_exec = rq_clock_task(rq) - curr->se.exec_start;
950 951
	if (unlikely((s64)delta_exec <= 0))
		return;
I
Ingo Molnar 已提交
952

953 954
	schedstat_set(curr->se.statistics.exec_max,
		      max(curr->se.statistics.exec_max, delta_exec));
I
Ingo Molnar 已提交
955 956

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

959
	curr->se.exec_start = rq_clock_task(rq);
960
	cpuacct_charge(curr, delta_exec);
P
Peter Zijlstra 已提交
961

962 963
	sched_rt_avg_update(rq, delta_exec);

964 965 966
	if (!rt_bandwidth_enabled())
		return;

D
Dhaval Giani 已提交
967
	for_each_sched_rt_entity(rt_se) {
968
		struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
D
Dhaval Giani 已提交
969

970
		if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
971
			raw_spin_lock(&rt_rq->rt_runtime_lock);
972 973
			rt_rq->rt_time += delta_exec;
			if (sched_rt_runtime_exceeded(rt_rq))
974
				resched_curr(rq);
975
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
976
		}
D
Dhaval Giani 已提交
977
	}
I
Ingo Molnar 已提交
978 979
}

980 981 982 983 984 985 986 987 988 989 990 991
static void
dequeue_top_rt_rq(struct rt_rq *rt_rq)
{
	struct rq *rq = rq_of_rt_rq(rt_rq);

	BUG_ON(&rq->rt != rt_rq);

	if (!rt_rq->rt_queued)
		return;

	BUG_ON(!rq->nr_running);

992
	sub_nr_running(rq, rt_rq->rt_nr_running);
993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007
	rt_rq->rt_queued = 0;
}

static void
enqueue_top_rt_rq(struct rt_rq *rt_rq)
{
	struct rq *rq = rq_of_rt_rq(rt_rq);

	BUG_ON(&rq->rt != rt_rq);

	if (rt_rq->rt_queued)
		return;
	if (rt_rq_throttled(rt_rq) || !rt_rq->rt_nr_running)
		return;

1008
	add_nr_running(rq, rt_rq->rt_nr_running);
1009 1010 1011
	rt_rq->rt_queued = 1;
}

1012
#if defined CONFIG_SMP
1013

1014 1015
static void
inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
1016
{
G
Gregory Haskins 已提交
1017
	struct rq *rq = rq_of_rt_rq(rt_rq);
1018

1019 1020 1021 1022 1023 1024 1025
#ifdef CONFIG_RT_GROUP_SCHED
	/*
	 * Change rq's cpupri only if rt_rq is the top queue.
	 */
	if (&rq->rt != rt_rq)
		return;
#endif
1026 1027
	if (rq->online && prio < prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
1028
}
1029

1030 1031 1032 1033
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);
1034

1035 1036 1037 1038 1039 1040 1041
#ifdef CONFIG_RT_GROUP_SCHED
	/*
	 * Change rq's cpupri only if rt_rq is the top queue.
	 */
	if (&rq->rt != rt_rq)
		return;
#endif
1042 1043
	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
1044 1045
}

1046 1047
#else /* CONFIG_SMP */

P
Peter Zijlstra 已提交
1048
static inline
1049 1050 1051 1052 1053
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 */
1054

1055
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
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 已提交
1072
	if (rt_rq->rt_nr_running) {
1073

1074
		WARN_ON(prio < prev_prio);
1075

1076
		/*
1077 1078
		 * This may have been our highest task, and therefore
		 * we may have some recomputation to do
1079
		 */
1080
		if (prio == prev_prio) {
1081 1082 1083
			struct rt_prio_array *array = &rt_rq->active;

			rt_rq->highest_prio.curr =
1084
				sched_find_first_bit(array->bitmap);
1085 1086
		}

1087
	} else
1088
		rt_rq->highest_prio.curr = MAX_RT_PRIO;
1089

1090 1091
	dec_rt_prio_smp(rt_rq, prio, prev_prio);
}
1092

1093 1094 1095 1096 1097 1098
#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 */
1099

1100
#ifdef CONFIG_RT_GROUP_SCHED
1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114

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 已提交
1115 1116 1117 1118
	if (rt_se_boosted(rt_se))
		rt_rq->rt_nr_boosted--;

	WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
}

#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 */

1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144
static inline
unsigned int rt_se_nr_running(struct sched_rt_entity *rt_se)
{
	struct rt_rq *group_rq = group_rt_rq(rt_se);

	if (group_rq)
		return group_rq->rt_nr_running;
	else
		return 1;
}

1145 1146 1147 1148 1149 1150
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));
1151
	rt_rq->rt_nr_running += rt_se_nr_running(rt_se);
1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162

	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);
1163
	rt_rq->rt_nr_running -= rt_se_nr_running(rt_se);
1164 1165 1166 1167

	dec_rt_prio(rt_rq, rt_se_prio(rt_se));
	dec_rt_migration(rt_se, rt_rq);
	dec_rt_group(rt_se, rt_rq);
1168 1169
}

1170
static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
I
Ingo Molnar 已提交
1171
{
P
Peter Zijlstra 已提交
1172 1173 1174
	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);
1175
	struct list_head *queue = array->queue + rt_se_prio(rt_se);
I
Ingo Molnar 已提交
1176

1177 1178 1179 1180 1181 1182 1183
	/*
	 * 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 已提交
1184
		return;
1185

1186 1187 1188 1189
	if (head)
		list_add(&rt_se->run_list, queue);
	else
		list_add_tail(&rt_se->run_list, queue);
P
Peter Zijlstra 已提交
1190
	__set_bit(rt_se_prio(rt_se), array->bitmap);
1191

P
Peter Zijlstra 已提交
1192 1193 1194
	inc_rt_tasks(rt_se, rt_rq);
}

1195
static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
P
Peter Zijlstra 已提交
1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210
{
	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.
 */
1211
static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
P
Peter Zijlstra 已提交
1212
{
1213
	struct sched_rt_entity *back = NULL;
P
Peter Zijlstra 已提交
1214

1215 1216 1217 1218 1219
	for_each_sched_rt_entity(rt_se) {
		rt_se->back = back;
		back = rt_se;
	}

1220 1221
	dequeue_top_rt_rq(rt_rq_of_se(back));

1222 1223
	for (rt_se = back; rt_se; rt_se = rt_se->back) {
		if (on_rt_rq(rt_se))
1224 1225 1226 1227
			__dequeue_rt_entity(rt_se);
	}
}

1228
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
1229
{
1230 1231
	struct rq *rq = rq_of_rt_se(rt_se);

1232 1233
	dequeue_rt_stack(rt_se);
	for_each_sched_rt_entity(rt_se)
1234
		__enqueue_rt_entity(rt_se, head);
1235
	enqueue_top_rt_rq(&rq->rt);
1236 1237 1238 1239
}

static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
1240 1241
	struct rq *rq = rq_of_rt_se(rt_se);

1242 1243 1244 1245 1246 1247
	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)
1248
			__enqueue_rt_entity(rt_se, false);
1249
	}
1250
	enqueue_top_rt_rq(&rq->rt);
I
Ingo Molnar 已提交
1251 1252 1253 1254 1255
}

/*
 * Adding/removing a task to/from a priority array:
 */
1256
static void
1257
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
P
Peter Zijlstra 已提交
1258 1259 1260
{
	struct sched_rt_entity *rt_se = &p->rt;

1261
	if (flags & ENQUEUE_WAKEUP)
P
Peter Zijlstra 已提交
1262 1263
		rt_se->timeout = 0;

1264
	enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
1265

1266
	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
1267
		enqueue_pushable_task(rq, p);
P
Peter Zijlstra 已提交
1268 1269
}

1270
static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1271
{
P
Peter Zijlstra 已提交
1272
	struct sched_rt_entity *rt_se = &p->rt;
I
Ingo Molnar 已提交
1273

1274
	update_curr_rt(rq);
1275
	dequeue_rt_entity(rt_se);
1276

1277
	dequeue_pushable_task(rq, p);
I
Ingo Molnar 已提交
1278 1279 1280
}

/*
1281 1282
 * Put task to the head or the end of the run list without the overhead of
 * dequeue followed by enqueue.
I
Ingo Molnar 已提交
1283
 */
1284 1285
static void
requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
P
Peter Zijlstra 已提交
1286
{
1287
	if (on_rt_rq(rt_se)) {
1288 1289 1290 1291 1292 1293 1294
		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);
1295
	}
P
Peter Zijlstra 已提交
1296 1297
}

1298
static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
I
Ingo Molnar 已提交
1299
{
P
Peter Zijlstra 已提交
1300 1301
	struct sched_rt_entity *rt_se = &p->rt;
	struct rt_rq *rt_rq;
I
Ingo Molnar 已提交
1302

P
Peter Zijlstra 已提交
1303 1304
	for_each_sched_rt_entity(rt_se) {
		rt_rq = rt_rq_of_se(rt_se);
1305
		requeue_rt_entity(rt_rq, rt_se, head);
P
Peter Zijlstra 已提交
1306
	}
I
Ingo Molnar 已提交
1307 1308
}

P
Peter Zijlstra 已提交
1309
static void yield_task_rt(struct rq *rq)
I
Ingo Molnar 已提交
1310
{
1311
	requeue_task_rt(rq, rq->curr, 0);
I
Ingo Molnar 已提交
1312 1313
}

1314
#ifdef CONFIG_SMP
1315 1316
static int find_lowest_rq(struct task_struct *task);

1317
static int
1318
select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags)
1319
{
1320 1321
	struct task_struct *curr;
	struct rq *rq;
1322 1323 1324 1325 1326

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

1327 1328 1329 1330 1331
	rq = cpu_rq(cpu);

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

1332
	/*
1333
	 * If the current task on @p's runqueue is an RT task, then
1334 1335 1336 1337
	 * try to see if we can wake this RT task up on another
	 * runqueue. Otherwise simply start this RT task
	 * on its current runqueue.
	 *
1338 1339 1340 1341 1342 1343 1344 1345 1346
	 * 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.
1347 1348 1349 1350 1351 1352
	 *
	 * 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.
1353
	 */
1354
	if (curr && unlikely(rt_task(curr)) &&
1355
	    (curr->nr_cpus_allowed < 2 ||
1356
	     curr->prio <= p->prio)) {
1357
		int target = find_lowest_rq(p);
1358

1359 1360 1361 1362 1363 1364
		/*
		 * Don't bother moving it if the destination CPU is
		 * not running a lower priority task.
		 */
		if (target != -1 &&
		    p->prio < cpu_rq(target)->rt.highest_prio.curr)
1365
			cpu = target;
1366
	}
1367
	rcu_read_unlock();
1368

1369
out:
1370
	return cpu;
1371
}
1372 1373 1374

static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
{
1375 1376 1377 1378 1379 1380
	/*
	 * Current can't be migrated, useless to reschedule,
	 * let's hope p can move out.
	 */
	if (rq->curr->nr_cpus_allowed == 1 ||
	    !cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
1381 1382
		return;

1383 1384 1385 1386
	/*
	 * p is migratable, so let's not schedule it and
	 * see if it is pushed or pulled somewhere else.
	 */
1387
	if (p->nr_cpus_allowed != 1
1388 1389
	    && cpupri_find(&rq->rd->cpupri, p, NULL))
		return;
1390

1391 1392 1393 1394 1395 1396
	/*
	 * 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);
1397
	resched_curr(rq);
1398 1399
}

1400 1401
#endif /* CONFIG_SMP */

I
Ingo Molnar 已提交
1402 1403 1404
/*
 * Preempt the current task with a newly woken task if needed:
 */
P
Peter Zijlstra 已提交
1405
static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1406
{
1407
	if (p->prio < rq->curr->prio) {
1408
		resched_curr(rq);
1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424
		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.
	 */
1425
	if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
1426
		check_preempt_equal_prio(rq, p);
1427
#endif
I
Ingo Molnar 已提交
1428 1429
}

P
Peter Zijlstra 已提交
1430 1431
static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
						   struct rt_rq *rt_rq)
I
Ingo Molnar 已提交
1432
{
P
Peter Zijlstra 已提交
1433 1434
	struct rt_prio_array *array = &rt_rq->active;
	struct sched_rt_entity *next = NULL;
I
Ingo Molnar 已提交
1435 1436 1437 1438
	struct list_head *queue;
	int idx;

	idx = sched_find_first_bit(array->bitmap);
P
Peter Zijlstra 已提交
1439
	BUG_ON(idx >= MAX_RT_PRIO);
I
Ingo Molnar 已提交
1440 1441

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

P
Peter Zijlstra 已提交
1444 1445
	return next;
}
I
Ingo Molnar 已提交
1446

1447
static struct task_struct *_pick_next_task_rt(struct rq *rq)
P
Peter Zijlstra 已提交
1448 1449 1450
{
	struct sched_rt_entity *rt_se;
	struct task_struct *p;
1451
	struct rt_rq *rt_rq  = &rq->rt;
P
Peter Zijlstra 已提交
1452 1453 1454

	do {
		rt_se = pick_next_rt_entity(rq, rt_rq);
1455
		BUG_ON(!rt_se);
P
Peter Zijlstra 已提交
1456 1457 1458 1459
		rt_rq = group_rt_rq(rt_se);
	} while (rt_rq);

	p = rt_task_of(rt_se);
1460
	p->se.exec_start = rq_clock_task(rq);
1461 1462 1463 1464

	return p;
}

1465 1466
static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev)
1467
{
1468 1469 1470
	struct task_struct *p;
	struct rt_rq *rt_rq = &rq->rt;

1471
	if (need_pull_rt_task(rq, prev)) {
1472
		pull_rt_task(rq);
1473 1474
		/*
		 * pull_rt_task() can drop (and re-acquire) rq->lock; this
1475 1476
		 * means a dl or stop task can slip in, in which case we need
		 * to re-start task selection.
1477
		 */
1478
		if (unlikely((rq->stop && task_on_rq_queued(rq->stop)) ||
1479
			     rq->dl.dl_nr_running))
1480 1481
			return RETRY_TASK;
	}
1482

1483 1484 1485 1486 1487 1488 1489
	/*
	 * We may dequeue prev's rt_rq in put_prev_task().
	 * So, we update time before rt_nr_running check.
	 */
	if (prev->sched_class == &rt_sched_class)
		update_curr_rt(rq);

1490
	if (!rt_rq->rt_queued)
1491 1492
		return NULL;

1493
	put_prev_task(rq, prev);
1494 1495

	p = _pick_next_task_rt(rq);
1496 1497

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

P
Peter Zijlstra 已提交
1500
	set_post_schedule(rq);
1501

P
Peter Zijlstra 已提交
1502
	return p;
I
Ingo Molnar 已提交
1503 1504
}

1505
static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
I
Ingo Molnar 已提交
1506
{
1507
	update_curr_rt(rq);
1508 1509 1510 1511 1512

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

1517
#ifdef CONFIG_SMP
P
Peter Zijlstra 已提交
1518

S
Steven Rostedt 已提交
1519 1520 1521
/* Only try algorithms three times */
#define RT_MAX_TRIES 3

1522 1523 1524
static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
{
	if (!task_running(rq, p) &&
1525
	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1526 1527 1528 1529
		return 1;
	return 0;
}

1530 1531 1532 1533 1534
/*
 * 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 已提交
1535
{
1536 1537
	struct plist_head *head = &rq->rt.pushable_tasks;
	struct task_struct *p;
1538

1539 1540
	if (!has_pushable_tasks(rq))
		return NULL;
1541

1542 1543 1544
	plist_for_each_entry(p, head, pushable_tasks) {
		if (pick_rt_task(rq, p, cpu))
			return p;
1545 1546
	}

1547
	return NULL;
S
Steven Rostedt 已提交
1548 1549
}

1550
static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
S
Steven Rostedt 已提交
1551

G
Gregory Haskins 已提交
1552 1553 1554
static int find_lowest_rq(struct task_struct *task)
{
	struct sched_domain *sd;
1555
	struct cpumask *lowest_mask = this_cpu_cpumask_var_ptr(local_cpu_mask);
G
Gregory Haskins 已提交
1556 1557
	int this_cpu = smp_processor_id();
	int cpu      = task_cpu(task);
G
Gregory Haskins 已提交
1558

1559 1560 1561 1562
	/* Make sure the mask is initialized first */
	if (unlikely(!lowest_mask))
		return -1;

1563
	if (task->nr_cpus_allowed == 1)
1564
		return -1; /* No other targets possible */
G
Gregory Haskins 已提交
1565

1566 1567
	if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
		return -1; /* No targets found */
G
Gregory Haskins 已提交
1568 1569 1570 1571 1572 1573 1574 1575 1576

	/*
	 * 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.
	 */
1577
	if (cpumask_test_cpu(cpu, lowest_mask))
G
Gregory Haskins 已提交
1578 1579 1580 1581 1582 1583
		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 已提交
1584 1585
	if (!cpumask_test_cpu(this_cpu, lowest_mask))
		this_cpu = -1; /* Skip this_cpu opt if not among lowest */
G
Gregory Haskins 已提交
1586

1587
	rcu_read_lock();
R
Rusty Russell 已提交
1588 1589 1590
	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_AFFINE) {
			int best_cpu;
G
Gregory Haskins 已提交
1591

R
Rusty Russell 已提交
1592 1593 1594 1595 1596
			/*
			 * "this_cpu" is cheaper to preempt than a
			 * remote processor.
			 */
			if (this_cpu != -1 &&
1597 1598
			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1599
				return this_cpu;
1600
			}
R
Rusty Russell 已提交
1601 1602 1603

			best_cpu = cpumask_first_and(lowest_mask,
						     sched_domain_span(sd));
1604 1605
			if (best_cpu < nr_cpu_ids) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1606
				return best_cpu;
1607
			}
G
Gregory Haskins 已提交
1608 1609
		}
	}
1610
	rcu_read_unlock();
G
Gregory Haskins 已提交
1611 1612 1613 1614 1615 1616

	/*
	 * 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 已提交
1617 1618 1619 1620 1621 1622 1623
	if (this_cpu != -1)
		return this_cpu;

	cpu = cpumask_any(lowest_mask);
	if (cpu < nr_cpu_ids)
		return cpu;
	return -1;
1624 1625 1626
}

/* Will lock the rq it finds */
1627
static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
1628 1629 1630
{
	struct rq *lowest_rq = NULL;
	int tries;
1631
	int cpu;
S
Steven Rostedt 已提交
1632

1633 1634 1635
	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
		cpu = find_lowest_rq(task);

1636
		if ((cpu == -1) || (cpu == rq->cpu))
S
Steven Rostedt 已提交
1637 1638
			break;

1639 1640
		lowest_rq = cpu_rq(cpu);

1641 1642 1643 1644 1645 1646 1647 1648 1649 1650
		if (lowest_rq->rt.highest_prio.curr <= task->prio) {
			/*
			 * Target rq has tasks of equal or higher priority,
			 * retrying does not release any lock and is unlikely
			 * to yield a different result.
			 */
			lowest_rq = NULL;
			break;
		}

S
Steven Rostedt 已提交
1651
		/* if the prio of this runqueue changed, try again */
1652
		if (double_lock_balance(rq, lowest_rq)) {
S
Steven Rostedt 已提交
1653 1654 1655 1656 1657 1658
			/*
			 * 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.
			 */
1659
			if (unlikely(task_rq(task) != rq ||
1660
				     !cpumask_test_cpu(lowest_rq->cpu,
1661
						       tsk_cpus_allowed(task)) ||
1662
				     task_running(rq, task) ||
1663
				     !task_on_rq_queued(task))) {
1664

1665
				double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1666 1667 1668 1669 1670 1671
				lowest_rq = NULL;
				break;
			}
		}

		/* If this rq is still suitable use it. */
1672
		if (lowest_rq->rt.highest_prio.curr > task->prio)
S
Steven Rostedt 已提交
1673 1674 1675
			break;

		/* try again */
1676
		double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1677 1678 1679 1680 1681 1682
		lowest_rq = NULL;
	}

	return lowest_rq;
}

1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694
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));
1695
	BUG_ON(p->nr_cpus_allowed <= 1);
1696

1697
	BUG_ON(!task_on_rq_queued(p));
1698 1699 1700 1701 1702
	BUG_ON(!rt_task(p));

	return p;
}

S
Steven Rostedt 已提交
1703 1704 1705 1706 1707
/*
 * 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.
 */
1708
static int push_rt_task(struct rq *rq)
S
Steven Rostedt 已提交
1709 1710 1711
{
	struct task_struct *next_task;
	struct rq *lowest_rq;
1712
	int ret = 0;
S
Steven Rostedt 已提交
1713

G
Gregory Haskins 已提交
1714 1715 1716
	if (!rq->rt.overloaded)
		return 0;

1717
	next_task = pick_next_pushable_task(rq);
S
Steven Rostedt 已提交
1718 1719 1720
	if (!next_task)
		return 0;

P
Peter Zijlstra 已提交
1721
retry:
1722
	if (unlikely(next_task == rq->curr)) {
1723
		WARN_ON(1);
S
Steven Rostedt 已提交
1724
		return 0;
1725
	}
S
Steven Rostedt 已提交
1726 1727 1728 1729 1730 1731

	/*
	 * It's possible that the next_task slipped in of
	 * higher priority than current. If that's the case
	 * just reschedule current.
	 */
1732
	if (unlikely(next_task->prio < rq->curr->prio)) {
1733
		resched_curr(rq);
S
Steven Rostedt 已提交
1734 1735 1736
		return 0;
	}

1737
	/* We might release rq lock */
S
Steven Rostedt 已提交
1738 1739 1740
	get_task_struct(next_task);

	/* find_lock_lowest_rq locks the rq if found */
1741
	lowest_rq = find_lock_lowest_rq(next_task, rq);
S
Steven Rostedt 已提交
1742 1743 1744
	if (!lowest_rq) {
		struct task_struct *task;
		/*
1745
		 * find_lock_lowest_rq releases rq->lock
1746 1747 1748 1749 1750
		 * 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 已提交
1751
		 */
1752
		task = pick_next_pushable_task(rq);
1753 1754
		if (task_cpu(next_task) == rq->cpu && task == next_task) {
			/*
1755 1756 1757 1758
			 * 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.
1759 1760
			 */
			goto out;
S
Steven Rostedt 已提交
1761
		}
1762

1763 1764 1765 1766
		if (!task)
			/* No more tasks, just exit */
			goto out;

1767
		/*
1768
		 * Something has shifted, try again.
1769
		 */
1770 1771 1772
		put_task_struct(next_task);
		next_task = task;
		goto retry;
S
Steven Rostedt 已提交
1773 1774
	}

1775
	deactivate_task(rq, next_task, 0);
S
Steven Rostedt 已提交
1776 1777
	set_task_cpu(next_task, lowest_rq->cpu);
	activate_task(lowest_rq, next_task, 0);
1778
	ret = 1;
S
Steven Rostedt 已提交
1779

1780
	resched_curr(lowest_rq);
S
Steven Rostedt 已提交
1781

1782
	double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1783 1784 1785 1786

out:
	put_task_struct(next_task);

1787
	return ret;
S
Steven Rostedt 已提交
1788 1789 1790 1791 1792 1793 1794 1795 1796
}

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

1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
#ifdef HAVE_RT_PUSH_IPI
/*
 * The search for the next cpu always starts at rq->cpu and ends
 * when we reach rq->cpu again. It will never return rq->cpu.
 * This returns the next cpu to check, or nr_cpu_ids if the loop
 * is complete.
 *
 * rq->rt.push_cpu holds the last cpu returned by this function,
 * or if this is the first instance, it must hold rq->cpu.
 */
static int rto_next_cpu(struct rq *rq)
{
	int prev_cpu = rq->rt.push_cpu;
	int cpu;

	cpu = cpumask_next(prev_cpu, rq->rd->rto_mask);

	/*
	 * If the previous cpu is less than the rq's CPU, then it already
	 * passed the end of the mask, and has started from the beginning.
	 * We end if the next CPU is greater or equal to rq's CPU.
	 */
	if (prev_cpu < rq->cpu) {
		if (cpu >= rq->cpu)
			return nr_cpu_ids;

	} else if (cpu >= nr_cpu_ids) {
		/*
		 * We passed the end of the mask, start at the beginning.
		 * If the result is greater or equal to the rq's CPU, then
		 * the loop is finished.
		 */
		cpu = cpumask_first(rq->rd->rto_mask);
		if (cpu >= rq->cpu)
			return nr_cpu_ids;
	}
	rq->rt.push_cpu = cpu;

	/* Return cpu to let the caller know if the loop is finished or not */
	return cpu;
}

static int find_next_push_cpu(struct rq *rq)
{
	struct rq *next_rq;
	int cpu;

	while (1) {
		cpu = rto_next_cpu(rq);
		if (cpu >= nr_cpu_ids)
			break;
		next_rq = cpu_rq(cpu);

		/* Make sure the next rq can push to this rq */
		if (next_rq->rt.highest_prio.next < rq->rt.highest_prio.curr)
			break;
	}

	return cpu;
}

#define RT_PUSH_IPI_EXECUTING		1
#define RT_PUSH_IPI_RESTART		2

static void tell_cpu_to_push(struct rq *rq)
{
	int cpu;

	if (rq->rt.push_flags & RT_PUSH_IPI_EXECUTING) {
		raw_spin_lock(&rq->rt.push_lock);
		/* Make sure it's still executing */
		if (rq->rt.push_flags & RT_PUSH_IPI_EXECUTING) {
			/*
			 * Tell the IPI to restart the loop as things have
			 * changed since it started.
			 */
			rq->rt.push_flags |= RT_PUSH_IPI_RESTART;
			raw_spin_unlock(&rq->rt.push_lock);
			return;
		}
		raw_spin_unlock(&rq->rt.push_lock);
	}

	/* When here, there's no IPI going around */

	rq->rt.push_cpu = rq->cpu;
	cpu = find_next_push_cpu(rq);
	if (cpu >= nr_cpu_ids)
		return;

	rq->rt.push_flags = RT_PUSH_IPI_EXECUTING;

	irq_work_queue_on(&rq->rt.push_work, cpu);
}

/* Called from hardirq context */
static void try_to_push_tasks(void *arg)
{
	struct rt_rq *rt_rq = arg;
	struct rq *rq, *src_rq;
	int this_cpu;
	int cpu;

	this_cpu = rt_rq->push_cpu;

	/* Paranoid check */
	BUG_ON(this_cpu != smp_processor_id());

	rq = cpu_rq(this_cpu);
	src_rq = rq_of_rt_rq(rt_rq);

again:
	if (has_pushable_tasks(rq)) {
		raw_spin_lock(&rq->lock);
		push_rt_task(rq);
		raw_spin_unlock(&rq->lock);
	}

	/* Pass the IPI to the next rt overloaded queue */
	raw_spin_lock(&rt_rq->push_lock);
	/*
	 * If the source queue changed since the IPI went out,
	 * we need to restart the search from that CPU again.
	 */
	if (rt_rq->push_flags & RT_PUSH_IPI_RESTART) {
		rt_rq->push_flags &= ~RT_PUSH_IPI_RESTART;
		rt_rq->push_cpu = src_rq->cpu;
	}

	cpu = find_next_push_cpu(src_rq);

	if (cpu >= nr_cpu_ids)
		rt_rq->push_flags &= ~RT_PUSH_IPI_EXECUTING;
	raw_spin_unlock(&rt_rq->push_lock);

	if (cpu >= nr_cpu_ids)
		return;

	/*
	 * It is possible that a restart caused this CPU to be
	 * chosen again. Don't bother with an IPI, just see if we
	 * have more to push.
	 */
	if (unlikely(cpu == rq->cpu))
		goto again;

	/* Try the next RT overloaded CPU */
	irq_work_queue_on(&rt_rq->push_work, cpu);
}

static void push_irq_work_func(struct irq_work *work)
{
	struct rt_rq *rt_rq = container_of(work, struct rt_rq, push_work);

	try_to_push_tasks(rt_rq);
}
#endif /* HAVE_RT_PUSH_IPI */

1955 1956
static int pull_rt_task(struct rq *this_rq)
{
I
Ingo Molnar 已提交
1957
	int this_cpu = this_rq->cpu, ret = 0, cpu;
1958
	struct task_struct *p;
1959 1960
	struct rq *src_rq;

1961
	if (likely(!rt_overloaded(this_rq)))
1962 1963
		return 0;

P
Peter Zijlstra 已提交
1964 1965 1966 1967 1968 1969
	/*
	 * Match the barrier from rt_set_overloaded; this guarantees that if we
	 * see overloaded we must also see the rto_mask bit.
	 */
	smp_rmb();

1970 1971 1972 1973 1974 1975 1976
#ifdef HAVE_RT_PUSH_IPI
	if (sched_feat(RT_PUSH_IPI)) {
		tell_cpu_to_push(this_rq);
		return 0;
	}
#endif

1977
	for_each_cpu(cpu, this_rq->rd->rto_mask) {
1978 1979 1980 1981
		if (this_cpu == cpu)
			continue;

		src_rq = cpu_rq(cpu);
1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993

		/*
		 * 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;

1994 1995 1996
		/*
		 * We can potentially drop this_rq's lock in
		 * double_lock_balance, and another CPU could
1997
		 * alter this_rq
1998
		 */
1999
		double_lock_balance(this_rq, src_rq);
2000 2001

		/*
2002 2003
		 * We can pull only a task, which is pushable
		 * on its rq, and no others.
2004
		 */
2005
		p = pick_highest_pushable_task(src_rq, this_cpu);
2006 2007 2008 2009 2010

		/*
		 * Do we have an RT task that preempts
		 * the to-be-scheduled task?
		 */
2011
		if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
2012
			WARN_ON(p == src_rq->curr);
2013
			WARN_ON(!task_on_rq_queued(p));
2014 2015 2016 2017 2018 2019 2020

			/*
			 * 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
2021
			 * current task on the run queue
2022
			 */
2023
			if (p->prio < src_rq->curr->prio)
M
Mike Galbraith 已提交
2024
				goto skip;
2025 2026 2027 2028 2029 2030 2031 2032 2033

			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 已提交
2034
			 * in another runqueue. (low likelihood
2035 2036 2037
			 * but possible)
			 */
		}
P
Peter Zijlstra 已提交
2038
skip:
2039
		double_unlock_balance(this_rq, src_rq);
2040 2041 2042 2043 2044
	}

	return ret;
}

2045
static void post_schedule_rt(struct rq *rq)
S
Steven Rostedt 已提交
2046
{
2047
	push_rt_tasks(rq);
S
Steven Rostedt 已提交
2048 2049
}

2050 2051 2052 2053
/*
 * If we are not running and we are not going to reschedule soon, we should
 * try to push tasks away now
 */
2054
static void task_woken_rt(struct rq *rq, struct task_struct *p)
2055
{
2056
	if (!task_running(rq, p) &&
2057
	    !test_tsk_need_resched(rq->curr) &&
2058
	    has_pushable_tasks(rq) &&
2059
	    p->nr_cpus_allowed > 1 &&
2060
	    (dl_task(rq->curr) || rt_task(rq->curr)) &&
2061
	    (rq->curr->nr_cpus_allowed < 2 ||
2062
	     rq->curr->prio <= p->prio))
2063 2064 2065
		push_rt_tasks(rq);
}

2066
static void set_cpus_allowed_rt(struct task_struct *p,
2067
				const struct cpumask *new_mask)
2068
{
2069 2070
	struct rq *rq;
	int weight;
2071 2072 2073

	BUG_ON(!rt_task(p));

2074
	if (!task_on_rq_queued(p))
2075
		return;
2076

2077
	weight = cpumask_weight(new_mask);
2078

2079 2080 2081 2082
	/*
	 * Only update if the process changes its state from whether it
	 * can migrate or not.
	 */
2083
	if ((p->nr_cpus_allowed > 1) == (weight > 1))
2084
		return;
2085

2086
	rq = task_rq(p);
2087

2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099
	/*
	 * 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++;
2100
	}
2101 2102

	update_rt_migration(&rq->rt);
2103
}
2104

2105
/* Assumes rq->lock is held */
2106
static void rq_online_rt(struct rq *rq)
2107 2108 2109
{
	if (rq->rt.overloaded)
		rt_set_overload(rq);
2110

P
Peter Zijlstra 已提交
2111 2112
	__enable_runtime(rq);

2113
	cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
2114 2115 2116
}

/* Assumes rq->lock is held */
2117
static void rq_offline_rt(struct rq *rq)
2118 2119 2120
{
	if (rq->rt.overloaded)
		rt_clear_overload(rq);
2121

P
Peter Zijlstra 已提交
2122 2123
	__disable_runtime(rq);

2124
	cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
2125
}
2126 2127 2128 2129 2130

/*
 * 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 已提交
2131
static void switched_from_rt(struct rq *rq, struct task_struct *p)
2132 2133 2134 2135 2136 2137 2138 2139
{
	/*
	 * 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.
	 */
2140
	if (!task_on_rq_queued(p) || rq->rt.rt_nr_running)
2141 2142 2143
		return;

	if (pull_rt_task(rq))
2144
		resched_curr(rq);
2145
}
2146

2147
void __init init_sched_rt_class(void)
2148 2149 2150
{
	unsigned int i;

2151
	for_each_possible_cpu(i) {
2152
		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
2153
					GFP_KERNEL, cpu_to_node(i));
2154
	}
2155
}
2156 2157 2158 2159 2160 2161 2162
#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 已提交
2163
static void switched_to_rt(struct rq *rq, struct task_struct *p)
2164 2165 2166 2167 2168 2169 2170 2171 2172 2173
{
	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.
	 */
2174
	if (task_on_rq_queued(p) && rq->curr != p) {
2175
#ifdef CONFIG_SMP
2176
		if (p->nr_cpus_allowed > 1 && rq->rt.overloaded &&
2177
		    /* Don't resched if we changed runqueues */
2178
		    push_rt_task(rq) && rq != task_rq(p))
2179 2180 2181
			check_resched = 0;
#endif /* CONFIG_SMP */
		if (check_resched && p->prio < rq->curr->prio)
2182
			resched_curr(rq);
2183 2184 2185 2186 2187 2188 2189
	}
}

/*
 * Priority of the task has changed. This may cause
 * us to initiate a push or pull.
 */
P
Peter Zijlstra 已提交
2190 2191
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
2192
{
2193
	if (!task_on_rq_queued(p))
P
Peter Zijlstra 已提交
2194 2195 2196
		return;

	if (rq->curr == p) {
2197 2198 2199 2200 2201 2202 2203 2204 2205
#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
2206 2207 2208
		 * 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.
2209
		 */
2210
		if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
2211
			resched_curr(rq);
2212 2213 2214
#else
		/* For UP simply resched on drop of prio */
		if (oldprio < p->prio)
2215
			resched_curr(rq);
S
Steven Rostedt 已提交
2216
#endif /* CONFIG_SMP */
2217 2218 2219 2220 2221 2222 2223
	} else {
		/*
		 * This task is not running, but if it is
		 * greater than the current running task
		 * then reschedule.
		 */
		if (p->prio < rq->curr->prio)
2224
			resched_curr(rq);
2225 2226 2227
	}
}

2228 2229 2230 2231
static void watchdog(struct rq *rq, struct task_struct *p)
{
	unsigned long soft, hard;

2232 2233 2234
	/* 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);
2235 2236 2237 2238

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

2239 2240 2241 2242 2243
		if (p->rt.watchdog_stamp != jiffies) {
			p->rt.timeout++;
			p->rt.watchdog_stamp = jiffies;
		}

2244
		next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
2245
		if (p->rt.timeout > next)
2246
			p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
2247 2248
	}
}
I
Ingo Molnar 已提交
2249

P
Peter Zijlstra 已提交
2250
static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
I
Ingo Molnar 已提交
2251
{
2252 2253
	struct sched_rt_entity *rt_se = &p->rt;

2254 2255
	update_curr_rt(rq);

2256 2257
	watchdog(rq, p);

I
Ingo Molnar 已提交
2258 2259 2260 2261 2262 2263 2264
	/*
	 * RR tasks need a special form of timeslice management.
	 * FIFO tasks have no timeslices.
	 */
	if (p->policy != SCHED_RR)
		return;

P
Peter Zijlstra 已提交
2265
	if (--p->rt.time_slice)
I
Ingo Molnar 已提交
2266 2267
		return;

2268
	p->rt.time_slice = sched_rr_timeslice;
I
Ingo Molnar 已提交
2269

2270
	/*
L
Li Bin 已提交
2271 2272
	 * Requeue to the end of queue if we (and all of our ancestors) are not
	 * the only element on the queue
2273
	 */
2274 2275 2276
	for_each_sched_rt_entity(rt_se) {
		if (rt_se->run_list.prev != rt_se->run_list.next) {
			requeue_task_rt(rq, p, 0);
2277
			resched_curr(rq);
2278 2279
			return;
		}
2280
	}
I
Ingo Molnar 已提交
2281 2282
}

2283 2284 2285 2286
static void set_curr_task_rt(struct rq *rq)
{
	struct task_struct *p = rq->curr;

2287
	p->se.exec_start = rq_clock_task(rq);
2288 2289 2290

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

2293
static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
2294 2295 2296 2297 2298
{
	/*
	 * Time slice is 0 for SCHED_FIFO tasks
	 */
	if (task->policy == SCHED_RR)
2299
		return sched_rr_timeslice;
2300 2301 2302 2303
	else
		return 0;
}

2304
const struct sched_class rt_sched_class = {
2305
	.next			= &fair_sched_class,
I
Ingo Molnar 已提交
2306 2307 2308 2309 2310 2311 2312 2313 2314
	.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,

2315
#ifdef CONFIG_SMP
L
Li Zefan 已提交
2316 2317
	.select_task_rq		= select_task_rq_rt,

2318
	.set_cpus_allowed       = set_cpus_allowed_rt,
2319 2320
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
2321
	.post_schedule		= post_schedule_rt,
2322
	.task_woken		= task_woken_rt,
2323
	.switched_from		= switched_from_rt,
2324
#endif
I
Ingo Molnar 已提交
2325

2326
	.set_curr_task          = set_curr_task_rt,
I
Ingo Molnar 已提交
2327
	.task_tick		= task_tick_rt,
2328

2329 2330
	.get_rr_interval	= get_rr_interval_rt,

2331 2332
	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,
2333 2334

	.update_curr		= update_curr_rt,
I
Ingo Molnar 已提交
2335
};
2336 2337 2338 2339

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

2340
void print_rt_stats(struct seq_file *m, int cpu)
2341
{
C
Cheng Xu 已提交
2342
	rt_rq_iter_t iter;
2343 2344 2345
	struct rt_rq *rt_rq;

	rcu_read_lock();
C
Cheng Xu 已提交
2346
	for_each_rt_rq(rt_rq, iter, cpu_rq(cpu))
2347 2348 2349
		print_rt_rq(m, cpu, rt_rq);
	rcu_read_unlock();
}
2350
#endif /* CONFIG_SCHED_DEBUG */