rt.c 46.3 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
static inline int rt_overloaded(struct rq *rq)
S
Steven Rostedt 已提交
233
{
234
	return atomic_read(&rq->rd->rto_count);
S
Steven Rostedt 已提交
235
}
I
Ingo Molnar 已提交
236

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

242
	cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
S
Steven Rostedt 已提交
243 244 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.
	 */
	wmb();
251
	atomic_inc(&rq->rd->rto_count);
S
Steven Rostedt 已提交
252
}
I
Ingo Molnar 已提交
253

S
Steven Rostedt 已提交
254 255
static inline void rt_clear_overload(struct rq *rq)
{
256 257 258
	if (!rq->online)
		return;

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

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

277 278
static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
279 280
	struct task_struct *p;

281 282 283
	if (!rt_entity_is_task(rt_se))
		return;

284
	p = rt_task_of(rt_se);
285 286 287
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total++;
288
	if (p->nr_cpus_allowed > 1)
289 290 291 292 293 294 295
		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)
{
296 297
	struct task_struct *p;

298 299 300
	if (!rt_entity_is_task(rt_se))
		return;

301
	p = rt_task_of(rt_se);
302 303 304
	rt_rq = &rq_of_rt_rq(rt_rq)->rt;

	rt_rq->rt_nr_total--;
305
	if (p->nr_cpus_allowed > 1)
306 307 308 309 310
		rt_rq->rt_nr_migratory--;

	update_rt_migration(rt_rq);
}

311 312 313 314 315
static inline int has_pushable_tasks(struct rq *rq)
{
	return !plist_head_empty(&rq->rt.pushable_tasks);
}

316 317 318 319 320
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);
321 322 323 324

	/* Update the highest prio pushable task */
	if (p->prio < rq->rt.highest_prio.next)
		rq->rt.highest_prio.next = p->prio;
325 326 327 328 329 330
}

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

331 332 333 334 335 336 337
	/* 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;
338 339
}

340 341
#else

342
static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
P
Peter Zijlstra 已提交
343
{
P
Peter Zijlstra 已提交
344 345
}

346 347 348 349
static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
{
}

350
static inline
351 352 353 354
void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
}

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

S
Steven Rostedt 已提交
360 361
#endif /* CONFIG_SMP */

P
Peter Zijlstra 已提交
362 363 364 365 366
static inline int on_rt_rq(struct sched_rt_entity *rt_se)
{
	return !list_empty(&rt_se->run_list);
}

367
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
368

P
Peter Zijlstra 已提交
369
static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
370 371
{
	if (!rt_rq->tg)
P
Peter Zijlstra 已提交
372
		return RUNTIME_INF;
P
Peter Zijlstra 已提交
373

P
Peter Zijlstra 已提交
374 375 376 377 378 379
	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 已提交
380 381
}

C
Cheng Xu 已提交
382 383
typedef struct task_group *rt_rq_iter_t;

384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
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 已提交
401

402 403 404 405 406 407 408 409 410 411 412
static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
{
	list_add_rcu(&rt_rq->leaf_rt_rq_list,
			&rq_of_rt_rq(rt_rq)->leaf_rt_rq_list);
}

static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
{
	list_del_rcu(&rt_rq->leaf_rt_rq_list);
}

P
Peter Zijlstra 已提交
413
#define for_each_leaf_rt_rq(rt_rq, rq) \
414
	list_for_each_entry_rcu(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
P
Peter Zijlstra 已提交
415 416 417 418 419 420 421 422 423

#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;
}

424
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head);
P
Peter Zijlstra 已提交
425 426
static void dequeue_rt_entity(struct sched_rt_entity *rt_se);

P
Peter Zijlstra 已提交
427
static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
428
{
429
	struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
430 431
	struct sched_rt_entity *rt_se;

432 433 434
	int cpu = cpu_of(rq_of_rt_rq(rt_rq));

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

436 437
	if (rt_rq->rt_nr_running) {
		if (rt_se && !on_rt_rq(rt_se))
438
			enqueue_rt_entity(rt_se, false);
439
		if (rt_rq->highest_prio.curr < curr->prio)
440
			resched_task(curr);
P
Peter Zijlstra 已提交
441 442 443
	}
}

P
Peter Zijlstra 已提交
444
static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
445
{
446
	struct sched_rt_entity *rt_se;
447
	int cpu = cpu_of(rq_of_rt_rq(rt_rq));
448

449
	rt_se = rt_rq->tg->rt_se[cpu];
P
Peter Zijlstra 已提交
450 451 452 453 454

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

P
Peter Zijlstra 已提交
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471
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;
}

472
#ifdef CONFIG_SMP
473
static inline const struct cpumask *sched_rt_period_mask(void)
474
{
N
Nathan Zimmer 已提交
475
	return this_rq()->rd->span;
476
}
P
Peter Zijlstra 已提交
477
#else
478
static inline const struct cpumask *sched_rt_period_mask(void)
479
{
480
	return cpu_online_mask;
481 482
}
#endif
P
Peter Zijlstra 已提交
483

484 485
static inline
struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu)
P
Peter Zijlstra 已提交
486
{
487 488
	return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu];
}
P
Peter Zijlstra 已提交
489

P
Peter Zijlstra 已提交
490 491 492 493 494
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &rt_rq->tg->rt_bandwidth;
}

495
#else /* !CONFIG_RT_GROUP_SCHED */
496 497 498

static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
{
P
Peter Zijlstra 已提交
499 500 501 502 503 504
	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 已提交
505 506
}

C
Cheng Xu 已提交
507 508 509 510 511
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)

512 513 514 515 516 517 518 519
static inline void list_add_leaf_rt_rq(struct rt_rq *rt_rq)
{
}

static inline void list_del_leaf_rt_rq(struct rt_rq *rt_rq)
{
}

P
Peter Zijlstra 已提交
520 521 522 523 524 525 526 527 528 529 530
#define for_each_leaf_rt_rq(rt_rq, rq) \
	for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)

#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 已提交
531
static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
532
{
533 534
	if (rt_rq->rt_nr_running)
		resched_task(rq_of_rt_rq(rt_rq)->curr);
P
Peter Zijlstra 已提交
535 536
}

P
Peter Zijlstra 已提交
537
static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
538 539 540
{
}

P
Peter Zijlstra 已提交
541 542 543 544
static inline int rt_rq_throttled(struct rt_rq *rt_rq)
{
	return rt_rq->rt_throttled;
}
545

546
static inline const struct cpumask *sched_rt_period_mask(void)
547
{
548
	return cpu_online_mask;
549 550 551 552 553 554 555 556
}

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 已提交
557 558 559 560 561
static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq)
{
	return &def_rt_bandwidth;
}

562
#endif /* CONFIG_RT_GROUP_SCHED */
563

P
Peter Zijlstra 已提交
564
#ifdef CONFIG_SMP
565 566 567
/*
 * We ran out of runtime, see if we can borrow some from our neighbours.
 */
568
static int do_balance_runtime(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
569 570
{
	struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
571
	struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd;
P
Peter Zijlstra 已提交
572 573 574
	int i, weight, more = 0;
	u64 rt_period;

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

577
	raw_spin_lock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
578
	rt_period = ktime_to_ns(rt_b->rt_period);
579
	for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
580 581 582 583 584 585
		struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
		s64 diff;

		if (iter == rt_rq)
			continue;

586
		raw_spin_lock(&iter->rt_runtime_lock);
587 588 589 590 591
		/*
		 * 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 已提交
592 593 594
		if (iter->rt_runtime == RUNTIME_INF)
			goto next;

595 596 597 598
		/*
		 * From runqueues with spare time, take 1/n part of their
		 * spare time, but no more than our period.
		 */
P
Peter Zijlstra 已提交
599 600
		diff = iter->rt_runtime - iter->rt_time;
		if (diff > 0) {
601
			diff = div_u64((u64)diff, weight);
P
Peter Zijlstra 已提交
602 603 604 605 606 607
			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) {
608
				raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
609 610 611
				break;
			}
		}
P
Peter Zijlstra 已提交
612
next:
613
		raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
614
	}
615
	raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
616 617 618

	return more;
}
P
Peter Zijlstra 已提交
619

620 621 622
/*
 * Ensure this RQ takes back all the runtime it lend to its neighbours.
 */
P
Peter Zijlstra 已提交
623 624 625
static void __disable_runtime(struct rq *rq)
{
	struct root_domain *rd = rq->rd;
C
Cheng Xu 已提交
626
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
627 628 629 630 631
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

C
Cheng Xu 已提交
632
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
633 634 635 636
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
		s64 want;
		int i;

637 638
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
639 640 641 642 643
		/*
		 * 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 已提交
644 645 646
		if (rt_rq->rt_runtime == RUNTIME_INF ||
				rt_rq->rt_runtime == rt_b->rt_runtime)
			goto balanced;
647
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
648

649 650 651 652 653
		/*
		 * 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 已提交
654 655
		want = rt_b->rt_runtime - rt_rq->rt_runtime;

656 657 658
		/*
		 * Greedy reclaim, take back as much as we can.
		 */
659
		for_each_cpu(i, rd->span) {
P
Peter Zijlstra 已提交
660 661 662
			struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
			s64 diff;

663 664 665
			/*
			 * Can't reclaim from ourselves or disabled runqueues.
			 */
666
			if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF)
P
Peter Zijlstra 已提交
667 668
				continue;

669
			raw_spin_lock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
670 671 672 673 674 675 676 677
			if (want > 0) {
				diff = min_t(s64, iter->rt_runtime, want);
				iter->rt_runtime -= diff;
				want -= diff;
			} else {
				iter->rt_runtime -= want;
				want -= want;
			}
678
			raw_spin_unlock(&iter->rt_runtime_lock);
P
Peter Zijlstra 已提交
679 680 681 682 683

			if (!want)
				break;
		}

684
		raw_spin_lock(&rt_rq->rt_runtime_lock);
685 686 687 688
		/*
		 * We cannot be left wanting - that would mean some runtime
		 * leaked out of the system.
		 */
P
Peter Zijlstra 已提交
689 690
		BUG_ON(want);
balanced:
691 692 693 694
		/*
		 * Disable all the borrow logic by pretending we have inf
		 * runtime - in which case borrowing doesn't make sense.
		 */
P
Peter Zijlstra 已提交
695
		rt_rq->rt_runtime = RUNTIME_INF;
696
		rt_rq->rt_throttled = 0;
697 698
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
699 700 701 702 703
	}
}

static void __enable_runtime(struct rq *rq)
{
C
Cheng Xu 已提交
704
	rt_rq_iter_t iter;
P
Peter Zijlstra 已提交
705 706 707 708 709
	struct rt_rq *rt_rq;

	if (unlikely(!scheduler_running))
		return;

710 711 712
	/*
	 * Reset each runqueue's bandwidth settings
	 */
C
Cheng Xu 已提交
713
	for_each_rt_rq(rt_rq, iter, rq) {
P
Peter Zijlstra 已提交
714 715
		struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

716 717
		raw_spin_lock(&rt_b->rt_runtime_lock);
		raw_spin_lock(&rt_rq->rt_runtime_lock);
P
Peter Zijlstra 已提交
718 719
		rt_rq->rt_runtime = rt_b->rt_runtime;
		rt_rq->rt_time = 0;
720
		rt_rq->rt_throttled = 0;
721 722
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
		raw_spin_unlock(&rt_b->rt_runtime_lock);
P
Peter Zijlstra 已提交
723 724 725
	}
}

726 727 728 729
static int balance_runtime(struct rt_rq *rt_rq)
{
	int more = 0;

730 731 732
	if (!sched_feat(RT_RUNTIME_SHARE))
		return more;

733
	if (rt_rq->rt_time > rt_rq->rt_runtime) {
734
		raw_spin_unlock(&rt_rq->rt_runtime_lock);
735
		more = do_balance_runtime(rt_rq);
736
		raw_spin_lock(&rt_rq->rt_runtime_lock);
737 738 739 740
	}

	return more;
}
741
#else /* !CONFIG_SMP */
742 743 744 745
static inline int balance_runtime(struct rt_rq *rt_rq)
{
	return 0;
}
746
#endif /* CONFIG_SMP */
P
Peter Zijlstra 已提交
747

748 749
static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
{
750
	int i, idle = 1, throttled = 0;
751
	const struct cpumask *span;
752 753

	span = sched_rt_period_mask();
754 755 756 757 758 759 760 761 762 763 764 765 766
#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
767
	for_each_cpu(i, span) {
768 769 770 771
		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);

772
		raw_spin_lock(&rq->lock);
773 774 775
		if (rt_rq->rt_time) {
			u64 runtime;

776
			raw_spin_lock(&rt_rq->rt_runtime_lock);
777 778 779 780 781 782 783
			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;
784 785 786 787 788 789 790

				/*
				 * 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;
791 792 793
			}
			if (rt_rq->rt_time || rt_rq->rt_nr_running)
				idle = 0;
794
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
795
		} else if (rt_rq->rt_nr_running) {
796
			idle = 0;
797 798 799
			if (!rt_rq_throttled(rt_rq))
				enqueue = 1;
		}
800 801
		if (rt_rq->rt_throttled)
			throttled = 1;
802 803 804

		if (enqueue)
			sched_rt_rq_enqueue(rt_rq);
805
		raw_spin_unlock(&rq->lock);
806 807
	}

808 809 810
	if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
		return 1;

811 812
	return idle;
}
P
Peter Zijlstra 已提交
813

P
Peter Zijlstra 已提交
814 815
static inline int rt_se_prio(struct sched_rt_entity *rt_se)
{
816
#ifdef CONFIG_RT_GROUP_SCHED
P
Peter Zijlstra 已提交
817 818 819
	struct rt_rq *rt_rq = group_rt_rq(rt_se);

	if (rt_rq)
820
		return rt_rq->highest_prio.curr;
P
Peter Zijlstra 已提交
821 822 823 824 825
#endif

	return rt_task_of(rt_se)->prio;
}

P
Peter Zijlstra 已提交
826
static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
P
Peter Zijlstra 已提交
827
{
P
Peter Zijlstra 已提交
828
	u64 runtime = sched_rt_runtime(rt_rq);
P
Peter Zijlstra 已提交
829 830

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

833
	if (runtime >= sched_rt_period(rt_rq))
P
Peter Zijlstra 已提交
834 835
		return 0;

836 837 838 839
	balance_runtime(rt_rq);
	runtime = sched_rt_runtime(rt_rq);
	if (runtime == RUNTIME_INF)
		return 0;
P
Peter Zijlstra 已提交
840

P
Peter Zijlstra 已提交
841
	if (rt_rq->rt_time > runtime) {
842 843 844 845 846 847 848
		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)) {
849 850
			static bool once = false;

851
			rt_rq->rt_throttled = 1;
852 853 854 855 856

			if (!once) {
				once = true;
				printk_sched("sched: RT throttling activated\n");
			}
857 858 859 860 861 862 863 864 865
		} 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 已提交
866
		if (rt_rq_throttled(rt_rq)) {
P
Peter Zijlstra 已提交
867
			sched_rt_rq_dequeue(rt_rq);
P
Peter Zijlstra 已提交
868 869
			return 1;
		}
P
Peter Zijlstra 已提交
870 871 872 873 874
	}

	return 0;
}

I
Ingo Molnar 已提交
875 876 877 878
/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
A
Alexey Dobriyan 已提交
879
static void update_curr_rt(struct rq *rq)
I
Ingo Molnar 已提交
880 881
{
	struct task_struct *curr = rq->curr;
P
Peter Zijlstra 已提交
882 883
	struct sched_rt_entity *rt_se = &curr->rt;
	struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
I
Ingo Molnar 已提交
884 885
	u64 delta_exec;

P
Peter Zijlstra 已提交
886
	if (curr->sched_class != &rt_sched_class)
I
Ingo Molnar 已提交
887 888
		return;

889
	delta_exec = rq->clock_task - curr->se.exec_start;
890 891
	if (unlikely((s64)delta_exec <= 0))
		return;
I
Ingo Molnar 已提交
892

893 894
	schedstat_set(curr->se.statistics.exec_max,
		      max(curr->se.statistics.exec_max, delta_exec));
I
Ingo Molnar 已提交
895 896

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

899
	curr->se.exec_start = rq->clock_task;
900
	cpuacct_charge(curr, delta_exec);
P
Peter Zijlstra 已提交
901

902 903
	sched_rt_avg_update(rq, delta_exec);

904 905 906
	if (!rt_bandwidth_enabled())
		return;

D
Dhaval Giani 已提交
907 908 909
	for_each_sched_rt_entity(rt_se) {
		rt_rq = rt_rq_of_se(rt_se);

910
		if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
911
			raw_spin_lock(&rt_rq->rt_runtime_lock);
912 913 914
			rt_rq->rt_time += delta_exec;
			if (sched_rt_runtime_exceeded(rt_rq))
				resched_task(curr);
915
			raw_spin_unlock(&rt_rq->rt_runtime_lock);
916
		}
D
Dhaval Giani 已提交
917
	}
I
Ingo Molnar 已提交
918 919
}

920
#if defined CONFIG_SMP
921

922 923
static void
inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
924
{
G
Gregory Haskins 已提交
925
	struct rq *rq = rq_of_rt_rq(rt_rq);
926

927 928
	if (rq->online && prio < prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
929
}
930

931 932 933 934
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);
935

936 937
	if (rq->online && rt_rq->highest_prio.curr != prev_prio)
		cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
938 939
}

940 941
#else /* CONFIG_SMP */

P
Peter Zijlstra 已提交
942
static inline
943 944 945 946 947
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 */
948

949
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965
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 已提交
966
	if (rt_rq->rt_nr_running) {
967

968
		WARN_ON(prio < prev_prio);
969

970
		/*
971 972
		 * This may have been our highest task, and therefore
		 * we may have some recomputation to do
973
		 */
974
		if (prio == prev_prio) {
975 976 977
			struct rt_prio_array *array = &rt_rq->active;

			rt_rq->highest_prio.curr =
978
				sched_find_first_bit(array->bitmap);
979 980
		}

981
	} else
982
		rt_rq->highest_prio.curr = MAX_RT_PRIO;
983

984 985
	dec_rt_prio_smp(rt_rq, prio, prev_prio);
}
986

987 988 989 990 991 992
#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 */
993

994
#ifdef CONFIG_RT_GROUP_SCHED
995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008

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 已提交
1009 1010 1011 1012
	if (rt_se_boosted(rt_se))
		rt_rq->rt_nr_boosted--;

	WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
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 1044 1045 1046 1047 1048 1049 1050
}

#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);
1051 1052
}

1053
static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
I
Ingo Molnar 已提交
1054
{
P
Peter Zijlstra 已提交
1055 1056 1057
	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);
1058
	struct list_head *queue = array->queue + rt_se_prio(rt_se);
I
Ingo Molnar 已提交
1059

1060 1061 1062 1063 1064 1065 1066
	/*
	 * 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 已提交
1067
		return;
1068

1069 1070 1071
	if (!rt_rq->rt_nr_running)
		list_add_leaf_rt_rq(rt_rq);

1072 1073 1074 1075
	if (head)
		list_add(&rt_se->run_list, queue);
	else
		list_add_tail(&rt_se->run_list, queue);
P
Peter Zijlstra 已提交
1076
	__set_bit(rt_se_prio(rt_se), array->bitmap);
1077

P
Peter Zijlstra 已提交
1078 1079 1080
	inc_rt_tasks(rt_se, rt_rq);
}

1081
static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
P
Peter Zijlstra 已提交
1082 1083 1084 1085 1086 1087 1088 1089 1090
{
	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);
1091 1092
	if (!rt_rq->rt_nr_running)
		list_del_leaf_rt_rq(rt_rq);
P
Peter Zijlstra 已提交
1093 1094 1095 1096 1097 1098
}

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

1103 1104 1105 1106 1107 1108 1109
	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))
1110 1111 1112 1113
			__dequeue_rt_entity(rt_se);
	}
}

1114
static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
1115 1116 1117
{
	dequeue_rt_stack(rt_se);
	for_each_sched_rt_entity(rt_se)
1118
		__enqueue_rt_entity(rt_se, head);
1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
}

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)
1129
			__enqueue_rt_entity(rt_se, false);
1130
	}
I
Ingo Molnar 已提交
1131 1132 1133 1134 1135
}

/*
 * Adding/removing a task to/from a priority array:
 */
1136
static void
1137
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
P
Peter Zijlstra 已提交
1138 1139 1140
{
	struct sched_rt_entity *rt_se = &p->rt;

1141
	if (flags & ENQUEUE_WAKEUP)
P
Peter Zijlstra 已提交
1142 1143
		rt_se->timeout = 0;

1144
	enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);
1145

1146
	if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
1147
		enqueue_pushable_task(rq, p);
1148 1149

	inc_nr_running(rq);
P
Peter Zijlstra 已提交
1150 1151
}

1152
static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1153
{
P
Peter Zijlstra 已提交
1154
	struct sched_rt_entity *rt_se = &p->rt;
I
Ingo Molnar 已提交
1155

1156
	update_curr_rt(rq);
1157
	dequeue_rt_entity(rt_se);
1158

1159
	dequeue_pushable_task(rq, p);
1160 1161

	dec_nr_running(rq);
I
Ingo Molnar 已提交
1162 1163 1164
}

/*
1165 1166
 * Put task to the head or the end of the run list without the overhead of
 * dequeue followed by enqueue.
I
Ingo Molnar 已提交
1167
 */
1168 1169
static void
requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
P
Peter Zijlstra 已提交
1170
{
1171
	if (on_rt_rq(rt_se)) {
1172 1173 1174 1175 1176 1177 1178
		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);
1179
	}
P
Peter Zijlstra 已提交
1180 1181
}

1182
static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
I
Ingo Molnar 已提交
1183
{
P
Peter Zijlstra 已提交
1184 1185
	struct sched_rt_entity *rt_se = &p->rt;
	struct rt_rq *rt_rq;
I
Ingo Molnar 已提交
1186

P
Peter Zijlstra 已提交
1187 1188
	for_each_sched_rt_entity(rt_se) {
		rt_rq = rt_rq_of_se(rt_se);
1189
		requeue_rt_entity(rt_rq, rt_se, head);
P
Peter Zijlstra 已提交
1190
	}
I
Ingo Molnar 已提交
1191 1192
}

P
Peter Zijlstra 已提交
1193
static void yield_task_rt(struct rq *rq)
I
Ingo Molnar 已提交
1194
{
1195
	requeue_task_rt(rq, rq->curr, 0);
I
Ingo Molnar 已提交
1196 1197
}

1198
#ifdef CONFIG_SMP
1199 1200
static int find_lowest_rq(struct task_struct *task);

1201
static int
1202
select_task_rq_rt(struct task_struct *p, int sd_flag, int flags)
1203
{
1204 1205 1206 1207 1208
	struct task_struct *curr;
	struct rq *rq;
	int cpu;

	cpu = task_cpu(p);
1209

1210
	if (p->nr_cpus_allowed == 1)
1211 1212
		goto out;

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

1217 1218 1219 1220 1221
	rq = cpu_rq(cpu);

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

1222
	/*
1223
	 * If the current task on @p's runqueue is an RT task, then
1224 1225 1226 1227
	 * try to see if we can wake this RT task up on another
	 * runqueue. Otherwise simply start this RT task
	 * on its current runqueue.
	 *
1228 1229 1230 1231 1232 1233 1234 1235 1236
	 * 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.
1237 1238 1239 1240 1241 1242
	 *
	 * 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.
1243
	 */
1244
	if (curr && unlikely(rt_task(curr)) &&
1245
	    (curr->nr_cpus_allowed < 2 ||
1246
	     curr->prio <= p->prio) &&
1247
	    (p->nr_cpus_allowed > 1)) {
1248
		int target = find_lowest_rq(p);
1249

1250 1251
		if (target != -1)
			cpu = target;
1252
	}
1253
	rcu_read_unlock();
1254

1255
out:
1256
	return cpu;
1257
}
1258 1259 1260

static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
{
1261
	if (rq->curr->nr_cpus_allowed == 1)
1262 1263
		return;

1264
	if (p->nr_cpus_allowed != 1
1265 1266
	    && cpupri_find(&rq->rd->cpupri, p, NULL))
		return;
1267

1268 1269
	if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
		return;
1270 1271 1272 1273 1274 1275 1276 1277 1278 1279

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

1280 1281
#endif /* CONFIG_SMP */

I
Ingo Molnar 已提交
1282 1283 1284
/*
 * Preempt the current task with a newly woken task if needed:
 */
P
Peter Zijlstra 已提交
1285
static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
I
Ingo Molnar 已提交
1286
{
1287
	if (p->prio < rq->curr->prio) {
I
Ingo Molnar 已提交
1288
		resched_task(rq->curr);
1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304
		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.
	 */
1305
	if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
1306
		check_preempt_equal_prio(rq, p);
1307
#endif
I
Ingo Molnar 已提交
1308 1309
}

P
Peter Zijlstra 已提交
1310 1311
static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
						   struct rt_rq *rt_rq)
I
Ingo Molnar 已提交
1312
{
P
Peter Zijlstra 已提交
1313 1314
	struct rt_prio_array *array = &rt_rq->active;
	struct sched_rt_entity *next = NULL;
I
Ingo Molnar 已提交
1315 1316 1317 1318
	struct list_head *queue;
	int idx;

	idx = sched_find_first_bit(array->bitmap);
P
Peter Zijlstra 已提交
1319
	BUG_ON(idx >= MAX_RT_PRIO);
I
Ingo Molnar 已提交
1320 1321

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

P
Peter Zijlstra 已提交
1324 1325
	return next;
}
I
Ingo Molnar 已提交
1326

1327
static struct task_struct *_pick_next_task_rt(struct rq *rq)
P
Peter Zijlstra 已提交
1328 1329 1330 1331
{
	struct sched_rt_entity *rt_se;
	struct task_struct *p;
	struct rt_rq *rt_rq;
I
Ingo Molnar 已提交
1332

P
Peter Zijlstra 已提交
1333 1334
	rt_rq = &rq->rt;

1335
	if (!rt_rq->rt_nr_running)
P
Peter Zijlstra 已提交
1336 1337
		return NULL;

P
Peter Zijlstra 已提交
1338
	if (rt_rq_throttled(rt_rq))
P
Peter Zijlstra 已提交
1339 1340 1341 1342
		return NULL;

	do {
		rt_se = pick_next_rt_entity(rq, rt_rq);
1343
		BUG_ON(!rt_se);
P
Peter Zijlstra 已提交
1344 1345 1346 1347
		rt_rq = group_rt_rq(rt_se);
	} while (rt_rq);

	p = rt_task_of(rt_se);
1348
	p->se.exec_start = rq->clock_task;
1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360

	return p;
}

static struct task_struct *pick_next_task_rt(struct rq *rq)
{
	struct task_struct *p = _pick_next_task_rt(rq);

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

1361
#ifdef CONFIG_SMP
1362 1363 1364 1365 1366
	/*
	 * 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);
1367
#endif
1368

P
Peter Zijlstra 已提交
1369
	return p;
I
Ingo Molnar 已提交
1370 1371
}

1372
static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
I
Ingo Molnar 已提交
1373
{
1374
	update_curr_rt(rq);
1375 1376 1377 1378 1379

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

1384
#ifdef CONFIG_SMP
P
Peter Zijlstra 已提交
1385

S
Steven Rostedt 已提交
1386 1387 1388
/* Only try algorithms three times */
#define RT_MAX_TRIES 3

1389 1390 1391
static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
{
	if (!task_running(rq, p) &&
1392
	    cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
1393 1394 1395 1396
		return 1;
	return 0;
}

S
Steven Rostedt 已提交
1397
/* Return the second highest RT task, NULL otherwise */
1398
static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu)
S
Steven Rostedt 已提交
1399
{
P
Peter Zijlstra 已提交
1400 1401 1402 1403
	struct task_struct *next = NULL;
	struct sched_rt_entity *rt_se;
	struct rt_prio_array *array;
	struct rt_rq *rt_rq;
S
Steven Rostedt 已提交
1404 1405
	int idx;

P
Peter Zijlstra 已提交
1406 1407 1408
	for_each_leaf_rt_rq(rt_rq, rq) {
		array = &rt_rq->active;
		idx = sched_find_first_bit(array->bitmap);
P
Peter Zijlstra 已提交
1409
next_idx:
P
Peter Zijlstra 已提交
1410 1411
		if (idx >= MAX_RT_PRIO)
			continue;
1412
		if (next && next->prio <= idx)
P
Peter Zijlstra 已提交
1413 1414
			continue;
		list_for_each_entry(rt_se, array->queue + idx, run_list) {
1415 1416 1417 1418 1419 1420
			struct task_struct *p;

			if (!rt_entity_is_task(rt_se))
				continue;

			p = rt_task_of(rt_se);
P
Peter Zijlstra 已提交
1421 1422 1423 1424 1425 1426 1427 1428 1429
			if (pick_rt_task(rq, p, cpu)) {
				next = p;
				break;
			}
		}
		if (!next) {
			idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1);
			goto next_idx;
		}
1430 1431
	}

S
Steven Rostedt 已提交
1432 1433 1434
	return next;
}

1435
static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask);
S
Steven Rostedt 已提交
1436

G
Gregory Haskins 已提交
1437 1438 1439
static int find_lowest_rq(struct task_struct *task)
{
	struct sched_domain *sd;
1440
	struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask);
G
Gregory Haskins 已提交
1441 1442
	int this_cpu = smp_processor_id();
	int cpu      = task_cpu(task);
G
Gregory Haskins 已提交
1443

1444 1445 1446 1447
	/* Make sure the mask is initialized first */
	if (unlikely(!lowest_mask))
		return -1;

1448
	if (task->nr_cpus_allowed == 1)
1449
		return -1; /* No other targets possible */
G
Gregory Haskins 已提交
1450

1451 1452
	if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask))
		return -1; /* No targets found */
G
Gregory Haskins 已提交
1453 1454 1455 1456 1457 1458 1459 1460 1461

	/*
	 * 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.
	 */
1462
	if (cpumask_test_cpu(cpu, lowest_mask))
G
Gregory Haskins 已提交
1463 1464 1465 1466 1467 1468
		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 已提交
1469 1470
	if (!cpumask_test_cpu(this_cpu, lowest_mask))
		this_cpu = -1; /* Skip this_cpu opt if not among lowest */
G
Gregory Haskins 已提交
1471

1472
	rcu_read_lock();
R
Rusty Russell 已提交
1473 1474 1475
	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_AFFINE) {
			int best_cpu;
G
Gregory Haskins 已提交
1476

R
Rusty Russell 已提交
1477 1478 1479 1480 1481
			/*
			 * "this_cpu" is cheaper to preempt than a
			 * remote processor.
			 */
			if (this_cpu != -1 &&
1482 1483
			    cpumask_test_cpu(this_cpu, sched_domain_span(sd))) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1484
				return this_cpu;
1485
			}
R
Rusty Russell 已提交
1486 1487 1488

			best_cpu = cpumask_first_and(lowest_mask,
						     sched_domain_span(sd));
1489 1490
			if (best_cpu < nr_cpu_ids) {
				rcu_read_unlock();
R
Rusty Russell 已提交
1491
				return best_cpu;
1492
			}
G
Gregory Haskins 已提交
1493 1494
		}
	}
1495
	rcu_read_unlock();
G
Gregory Haskins 已提交
1496 1497 1498 1499 1500 1501

	/*
	 * 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 已提交
1502 1503 1504 1505 1506 1507 1508
	if (this_cpu != -1)
		return this_cpu;

	cpu = cpumask_any(lowest_mask);
	if (cpu < nr_cpu_ids)
		return cpu;
	return -1;
1509 1510 1511
}

/* Will lock the rq it finds */
1512
static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
1513 1514 1515
{
	struct rq *lowest_rq = NULL;
	int tries;
1516
	int cpu;
S
Steven Rostedt 已提交
1517

1518 1519 1520
	for (tries = 0; tries < RT_MAX_TRIES; tries++) {
		cpu = find_lowest_rq(task);

1521
		if ((cpu == -1) || (cpu == rq->cpu))
S
Steven Rostedt 已提交
1522 1523
			break;

1524 1525
		lowest_rq = cpu_rq(cpu);

S
Steven Rostedt 已提交
1526
		/* if the prio of this runqueue changed, try again */
1527
		if (double_lock_balance(rq, lowest_rq)) {
S
Steven Rostedt 已提交
1528 1529 1530 1531 1532 1533
			/*
			 * 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.
			 */
1534
			if (unlikely(task_rq(task) != rq ||
1535
				     !cpumask_test_cpu(lowest_rq->cpu,
1536
						       tsk_cpus_allowed(task)) ||
1537
				     task_running(rq, task) ||
P
Peter Zijlstra 已提交
1538
				     !task->on_rq)) {
1539

1540
				double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1541 1542 1543 1544 1545 1546
				lowest_rq = NULL;
				break;
			}
		}

		/* If this rq is still suitable use it. */
1547
		if (lowest_rq->rt.highest_prio.curr > task->prio)
S
Steven Rostedt 已提交
1548 1549 1550
			break;

		/* try again */
1551
		double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1552 1553 1554 1555 1556 1557
		lowest_rq = NULL;
	}

	return lowest_rq;
}

1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569
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));
1570
	BUG_ON(p->nr_cpus_allowed <= 1);
1571

P
Peter Zijlstra 已提交
1572
	BUG_ON(!p->on_rq);
1573 1574 1575 1576 1577
	BUG_ON(!rt_task(p));

	return p;
}

S
Steven Rostedt 已提交
1578 1579 1580 1581 1582
/*
 * 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.
 */
1583
static int push_rt_task(struct rq *rq)
S
Steven Rostedt 已提交
1584 1585 1586
{
	struct task_struct *next_task;
	struct rq *lowest_rq;
1587
	int ret = 0;
S
Steven Rostedt 已提交
1588

G
Gregory Haskins 已提交
1589 1590 1591
	if (!rq->rt.overloaded)
		return 0;

1592
	next_task = pick_next_pushable_task(rq);
S
Steven Rostedt 已提交
1593 1594 1595
	if (!next_task)
		return 0;

P
Peter Zijlstra 已提交
1596
retry:
1597
	if (unlikely(next_task == rq->curr)) {
1598
		WARN_ON(1);
S
Steven Rostedt 已提交
1599
		return 0;
1600
	}
S
Steven Rostedt 已提交
1601 1602 1603 1604 1605 1606

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

1612
	/* We might release rq lock */
S
Steven Rostedt 已提交
1613 1614 1615
	get_task_struct(next_task);

	/* find_lock_lowest_rq locks the rq if found */
1616
	lowest_rq = find_lock_lowest_rq(next_task, rq);
S
Steven Rostedt 已提交
1617 1618 1619
	if (!lowest_rq) {
		struct task_struct *task;
		/*
1620
		 * find_lock_lowest_rq releases rq->lock
1621 1622 1623 1624 1625
		 * 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 已提交
1626
		 */
1627
		task = pick_next_pushable_task(rq);
1628 1629
		if (task_cpu(next_task) == rq->cpu && task == next_task) {
			/*
1630 1631 1632 1633
			 * 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.
1634 1635
			 */
			goto out;
S
Steven Rostedt 已提交
1636
		}
1637

1638 1639 1640 1641
		if (!task)
			/* No more tasks, just exit */
			goto out;

1642
		/*
1643
		 * Something has shifted, try again.
1644
		 */
1645 1646 1647
		put_task_struct(next_task);
		next_task = task;
		goto retry;
S
Steven Rostedt 已提交
1648 1649
	}

1650
	deactivate_task(rq, next_task, 0);
S
Steven Rostedt 已提交
1651 1652
	set_task_cpu(next_task, lowest_rq->cpu);
	activate_task(lowest_rq, next_task, 0);
1653
	ret = 1;
S
Steven Rostedt 已提交
1654 1655 1656

	resched_task(lowest_rq->curr);

1657
	double_unlock_balance(rq, lowest_rq);
S
Steven Rostedt 已提交
1658 1659 1660 1661

out:
	put_task_struct(next_task);

1662
	return ret;
S
Steven Rostedt 已提交
1663 1664 1665 1666 1667 1668 1669 1670 1671
}

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

1672 1673
static int pull_rt_task(struct rq *this_rq)
{
I
Ingo Molnar 已提交
1674
	int this_cpu = this_rq->cpu, ret = 0, cpu;
1675
	struct task_struct *p;
1676 1677
	struct rq *src_rq;

1678
	if (likely(!rt_overloaded(this_rq)))
1679 1680
		return 0;

1681
	for_each_cpu(cpu, this_rq->rd->rto_mask) {
1682 1683 1684 1685
		if (this_cpu == cpu)
			continue;

		src_rq = cpu_rq(cpu);
1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697

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

1698 1699 1700
		/*
		 * We can potentially drop this_rq's lock in
		 * double_lock_balance, and another CPU could
1701
		 * alter this_rq
1702
		 */
1703
		double_lock_balance(this_rq, src_rq);
1704 1705 1706 1707

		/*
		 * Are there still pullable RT tasks?
		 */
M
Mike Galbraith 已提交
1708 1709
		if (src_rq->rt.rt_nr_running <= 1)
			goto skip;
1710 1711 1712 1713 1714 1715 1716

		p = pick_next_highest_task_rt(src_rq, this_cpu);

		/*
		 * Do we have an RT task that preempts
		 * the to-be-scheduled task?
		 */
1717
		if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
1718
			WARN_ON(p == src_rq->curr);
P
Peter Zijlstra 已提交
1719
			WARN_ON(!p->on_rq);
1720 1721 1722 1723 1724 1725 1726

			/*
			 * 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
1727
			 * current task on the run queue
1728
			 */
1729
			if (p->prio < src_rq->curr->prio)
M
Mike Galbraith 已提交
1730
				goto skip;
1731 1732 1733 1734 1735 1736 1737 1738 1739

			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 已提交
1740
			 * in another runqueue. (low likelihood
1741 1742 1743
			 * but possible)
			 */
		}
P
Peter Zijlstra 已提交
1744
skip:
1745
		double_unlock_balance(this_rq, src_rq);
1746 1747 1748 1749 1750
	}

	return ret;
}

1751
static void pre_schedule_rt(struct rq *rq, struct task_struct *prev)
1752 1753
{
	/* Try to pull RT tasks here if we lower this rq's prio */
Y
Yong Zhang 已提交
1754
	if (rq->rt.highest_prio.curr > prev->prio)
1755 1756 1757
		pull_rt_task(rq);
}

1758
static void post_schedule_rt(struct rq *rq)
S
Steven Rostedt 已提交
1759
{
1760
	push_rt_tasks(rq);
S
Steven Rostedt 已提交
1761 1762
}

1763 1764 1765 1766
/*
 * If we are not running and we are not going to reschedule soon, we should
 * try to push tasks away now
 */
1767
static void task_woken_rt(struct rq *rq, struct task_struct *p)
1768
{
1769
	if (!task_running(rq, p) &&
1770
	    !test_tsk_need_resched(rq->curr) &&
1771
	    has_pushable_tasks(rq) &&
1772
	    p->nr_cpus_allowed > 1 &&
1773
	    rt_task(rq->curr) &&
1774
	    (rq->curr->nr_cpus_allowed < 2 ||
1775
	     rq->curr->prio <= p->prio))
1776 1777 1778
		push_rt_tasks(rq);
}

1779
static void set_cpus_allowed_rt(struct task_struct *p,
1780
				const struct cpumask *new_mask)
1781
{
1782 1783
	struct rq *rq;
	int weight;
1784 1785 1786

	BUG_ON(!rt_task(p));

1787 1788
	if (!p->on_rq)
		return;
1789

1790
	weight = cpumask_weight(new_mask);
1791

1792 1793 1794 1795
	/*
	 * Only update if the process changes its state from whether it
	 * can migrate or not.
	 */
1796
	if ((p->nr_cpus_allowed > 1) == (weight > 1))
1797
		return;
1798

1799
	rq = task_rq(p);
1800

1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812
	/*
	 * 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++;
1813
	}
1814 1815

	update_rt_migration(&rq->rt);
1816
}
1817

1818
/* Assumes rq->lock is held */
1819
static void rq_online_rt(struct rq *rq)
1820 1821 1822
{
	if (rq->rt.overloaded)
		rt_set_overload(rq);
1823

P
Peter Zijlstra 已提交
1824 1825
	__enable_runtime(rq);

1826
	cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr);
1827 1828 1829
}

/* Assumes rq->lock is held */
1830
static void rq_offline_rt(struct rq *rq)
1831 1832 1833
{
	if (rq->rt.overloaded)
		rt_clear_overload(rq);
1834

P
Peter Zijlstra 已提交
1835 1836
	__disable_runtime(rq);

1837
	cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID);
1838
}
1839 1840 1841 1842 1843

/*
 * 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 已提交
1844
static void switched_from_rt(struct rq *rq, struct task_struct *p)
1845 1846 1847 1848 1849 1850 1851 1852
{
	/*
	 * 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.
	 */
1853 1854 1855 1856 1857
	if (!p->on_rq || rq->rt.rt_nr_running)
		return;

	if (pull_rt_task(rq))
		resched_task(rq->curr);
1858
}
1859

1860
void init_sched_rt_class(void)
1861 1862 1863
{
	unsigned int i;

1864
	for_each_possible_cpu(i) {
1865
		zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i),
1866
					GFP_KERNEL, cpu_to_node(i));
1867
	}
1868
}
1869 1870 1871 1872 1873 1874 1875
#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 已提交
1876
static void switched_to_rt(struct rq *rq, struct task_struct *p)
1877 1878 1879 1880 1881 1882 1883 1884 1885 1886
{
	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 已提交
1887
	if (p->on_rq && rq->curr != p) {
1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902
#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 已提交
1903 1904
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
1905
{
P
Peter Zijlstra 已提交
1906
	if (!p->on_rq)
P
Peter Zijlstra 已提交
1907 1908 1909
		return;

	if (rq->curr == p) {
1910 1911 1912 1913 1914 1915 1916 1917 1918
#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
1919 1920 1921
		 * 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.
1922
		 */
1923
		if (p->prio > rq->rt.highest_prio.curr && rq->curr == p)
1924 1925 1926 1927 1928
			resched_task(p);
#else
		/* For UP simply resched on drop of prio */
		if (oldprio < p->prio)
			resched_task(p);
S
Steven Rostedt 已提交
1929
#endif /* CONFIG_SMP */
1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940
	} 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);
	}
}

1941 1942 1943 1944
static void watchdog(struct rq *rq, struct task_struct *p)
{
	unsigned long soft, hard;

1945 1946 1947
	/* 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);
1948 1949 1950 1951

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

1952 1953 1954 1955 1956
		if (p->rt.watchdog_stamp != jiffies) {
			p->rt.timeout++;
			p->rt.watchdog_stamp = jiffies;
		}

1957
		next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
1958
		if (p->rt.timeout > next)
1959
			p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
1960 1961
	}
}
I
Ingo Molnar 已提交
1962

P
Peter Zijlstra 已提交
1963
static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
I
Ingo Molnar 已提交
1964
{
1965 1966
	struct sched_rt_entity *rt_se = &p->rt;

1967 1968
	update_curr_rt(rq);

1969 1970
	watchdog(rq, p);

I
Ingo Molnar 已提交
1971 1972 1973 1974 1975 1976 1977
	/*
	 * RR tasks need a special form of timeslice management.
	 * FIFO tasks have no timeslices.
	 */
	if (p->policy != SCHED_RR)
		return;

P
Peter Zijlstra 已提交
1978
	if (--p->rt.time_slice)
I
Ingo Molnar 已提交
1979 1980
		return;

1981
	p->rt.time_slice = sched_rr_timeslice;
I
Ingo Molnar 已提交
1982

1983
	/*
1984 1985
	 * Requeue to the end of queue if we (and all of our ancestors) are the
	 * only element on the queue
1986
	 */
1987 1988 1989 1990 1991 1992
	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;
		}
1993
	}
I
Ingo Molnar 已提交
1994 1995
}

1996 1997 1998 1999
static void set_curr_task_rt(struct rq *rq)
{
	struct task_struct *p = rq->curr;

2000
	p->se.exec_start = rq->clock_task;
2001 2002 2003

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

2006
static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
2007 2008 2009 2010 2011
{
	/*
	 * Time slice is 0 for SCHED_FIFO tasks
	 */
	if (task->policy == SCHED_RR)
2012
		return sched_rr_timeslice;
2013 2014 2015 2016
	else
		return 0;
}

2017
const struct sched_class rt_sched_class = {
2018
	.next			= &fair_sched_class,
I
Ingo Molnar 已提交
2019 2020 2021 2022 2023 2024 2025 2026 2027
	.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,

2028
#ifdef CONFIG_SMP
L
Li Zefan 已提交
2029 2030
	.select_task_rq		= select_task_rq_rt,

2031
	.set_cpus_allowed       = set_cpus_allowed_rt,
2032 2033
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
2034 2035
	.pre_schedule		= pre_schedule_rt,
	.post_schedule		= post_schedule_rt,
2036
	.task_woken		= task_woken_rt,
2037
	.switched_from		= switched_from_rt,
2038
#endif
I
Ingo Molnar 已提交
2039

2040
	.set_curr_task          = set_curr_task_rt,
I
Ingo Molnar 已提交
2041
	.task_tick		= task_tick_rt,
2042

2043 2044
	.get_rr_interval	= get_rr_interval_rt,

2045 2046
	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,
I
Ingo Molnar 已提交
2047
};
2048 2049 2050 2051

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

2052
void print_rt_stats(struct seq_file *m, int cpu)
2053
{
C
Cheng Xu 已提交
2054
	rt_rq_iter_t iter;
2055 2056 2057
	struct rt_rq *rt_rq;

	rcu_read_lock();
C
Cheng Xu 已提交
2058
	for_each_rt_rq(rt_rq, iter, cpu_rq(cpu))
2059 2060 2061
		print_rt_rq(m, cpu, rt_rq);
	rcu_read_unlock();
}
2062
#endif /* CONFIG_SCHED_DEBUG */