sched_fair.c 40.9 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/*
 * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
 *
 *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
 *
 *  Interactivity improvements by Mike Galbraith
 *  (C) 2007 Mike Galbraith <efault@gmx.de>
 *
 *  Various enhancements by Dmitry Adamushko.
 *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
 *
 *  Group scheduling enhancements by Srivatsa Vaddagiri
 *  Copyright IBM Corporation, 2007
 *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
 *
 *  Scaled math optimizations by Thomas Gleixner
 *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
18 19 20
 *
 *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
 *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
21 22
 */

A
Arjan van de Ven 已提交
23 24
#include <linux/latencytop.h>

25
/*
26
 * Targeted preemption latency for CPU-bound tasks:
27
 * (default: 20ms * (1 + ilog(ncpus)), units: nanoseconds)
28
 *
29
 * NOTE: this latency value is not the same as the concept of
I
Ingo Molnar 已提交
30 31 32
 * 'timeslice length' - timeslices in CFS are of variable length
 * and have no persistent notion like in traditional, time-slice
 * based scheduling concepts.
33
 *
I
Ingo Molnar 已提交
34 35
 * (to see the precise effective timeslice length of your workload,
 *  run vmstat and monitor the context-switches (cs) field)
36
 */
I
Ingo Molnar 已提交
37
unsigned int sysctl_sched_latency = 20000000ULL;
38 39

/*
40
 * Minimal preemption granularity for CPU-bound tasks:
41
 * (default: 4 msec * (1 + ilog(ncpus)), units: nanoseconds)
42
 */
43
unsigned int sysctl_sched_min_granularity = 4000000ULL;
44 45

/*
46 47
 * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
 */
48
static unsigned int sched_nr_latency = 5;
49 50 51 52

/*
 * After fork, child runs first. (default) If set to 0 then
 * parent will (try to) run first.
53
 */
54
const_debug unsigned int sysctl_sched_child_runs_first = 1;
55

56 57 58 59 60 61 62 63
/*
 * sys_sched_yield() compat mode
 *
 * This option switches the agressive yield implementation of the
 * old scheduler back on.
 */
unsigned int __read_mostly sysctl_sched_compat_yield;

64 65
/*
 * SCHED_OTHER wake-up granularity.
66
 * (default: 5 msec * (1 + ilog(ncpus)), units: nanoseconds)
67 68 69 70 71
 *
 * This option delays the preemption effects of decoupled workloads
 * and reduces their over-scheduling. Synchronous workloads will still
 * have immediate wakeup/sleep latencies.
 */
72
unsigned int sysctl_sched_wakeup_granularity = 5000000UL;
73

74 75
const_debug unsigned int sysctl_sched_migration_cost = 500000UL;

76 77
static const struct sched_class fair_sched_class;

78 79 80 81
/**************************************************************
 * CFS operations on generic schedulable entities:
 */

P
Peter Zijlstra 已提交
82 83 84 85 86
static inline struct task_struct *task_of(struct sched_entity *se)
{
	return container_of(se, struct task_struct, se);
}

87
#ifdef CONFIG_FAIR_GROUP_SCHED
88

89
/* cpu runqueue to which this cfs_rq is attached */
90 91
static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
{
92
	return cfs_rq->rq;
93 94
}

95 96
/* An entity is a task if it doesn't "own" a runqueue */
#define entity_is_task(se)	(!se->my_q)
97

P
Peter Zijlstra 已提交
98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 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
/* Walk up scheduling entities hierarchy */
#define for_each_sched_entity(se) \
		for (; se; se = se->parent)

static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
{
	return p->se.cfs_rq;
}

/* runqueue on which this entity is (to be) queued */
static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
{
	return se->cfs_rq;
}

/* runqueue "owned" by this group */
static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
	return grp->my_q;
}

/* Given a group's cfs_rq on one cpu, return its corresponding cfs_rq on
 * another cpu ('this_cpu')
 */
static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
{
	return cfs_rq->tg->cfs_rq[this_cpu];
}

/* Iterate thr' all leaf cfs_rq's on a runqueue */
#define for_each_leaf_cfs_rq(rq, cfs_rq) \
	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)

/* Do the two (enqueued) entities belong to the same group ? */
static inline int
is_same_group(struct sched_entity *se, struct sched_entity *pse)
{
	if (se->cfs_rq == pse->cfs_rq)
		return 1;

	return 0;
}

static inline struct sched_entity *parent_entity(struct sched_entity *se)
{
	return se->parent;
}

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
/* return depth at which a sched entity is present in the hierarchy */
static inline int depth_se(struct sched_entity *se)
{
	int depth = 0;

	for_each_sched_entity(se)
		depth++;

	return depth;
}

static void
find_matching_se(struct sched_entity **se, struct sched_entity **pse)
{
	int se_depth, pse_depth;

	/*
	 * preemption test can be made between sibling entities who are in the
	 * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
	 * both tasks until we find their ancestors who are siblings of common
	 * parent.
	 */

	/* First walk up until both entities are at same depth */
	se_depth = depth_se(*se);
	pse_depth = depth_se(*pse);

	while (se_depth > pse_depth) {
		se_depth--;
		*se = parent_entity(*se);
	}

	while (pse_depth > se_depth) {
		pse_depth--;
		*pse = parent_entity(*pse);
	}

	while (!is_same_group(*se, *pse)) {
		*se = parent_entity(*se);
		*pse = parent_entity(*pse);
	}
}

189
#else	/* CONFIG_FAIR_GROUP_SCHED */
190

191 192 193
static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
{
	return container_of(cfs_rq, struct rq, cfs);
194 195 196 197
}

#define entity_is_task(se)	1

P
Peter Zijlstra 已提交
198 199
#define for_each_sched_entity(se) \
		for (; se; se = NULL)
200

P
Peter Zijlstra 已提交
201
static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
202
{
P
Peter Zijlstra 已提交
203
	return &task_rq(p)->cfs;
204 205
}

P
Peter Zijlstra 已提交
206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
{
	struct task_struct *p = task_of(se);
	struct rq *rq = task_rq(p);

	return &rq->cfs;
}

/* runqueue "owned" by this group */
static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
	return NULL;
}

static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)
{
	return &cpu_rq(this_cpu)->cfs;
}

#define for_each_leaf_cfs_rq(rq, cfs_rq) \
		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)

static inline int
is_same_group(struct sched_entity *se, struct sched_entity *pse)
{
	return 1;
}

static inline struct sched_entity *parent_entity(struct sched_entity *se)
{
	return NULL;
}

239 240 241 242 243
static inline void
find_matching_se(struct sched_entity **se, struct sched_entity **pse)
{
}

P
Peter Zijlstra 已提交
244 245
#endif	/* CONFIG_FAIR_GROUP_SCHED */

246 247 248 249 250

/**************************************************************
 * Scheduling class tree data structure manipulation methods:
 */

251
static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
252
{
253 254
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta > 0)
255 256 257 258 259
		min_vruntime = vruntime;

	return min_vruntime;
}

260
static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
P
Peter Zijlstra 已提交
261 262 263 264 265 266 267 268
{
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta < 0)
		min_vruntime = vruntime;

	return min_vruntime;
}

269
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
270
{
271
	return se->vruntime - cfs_rq->min_vruntime;
272 273
}

274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	u64 vruntime = cfs_rq->min_vruntime;

	if (cfs_rq->curr)
		vruntime = cfs_rq->curr->vruntime;

	if (cfs_rq->rb_leftmost) {
		struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
						   struct sched_entity,
						   run_node);

		if (vruntime == cfs_rq->min_vruntime)
			vruntime = se->vruntime;
		else
			vruntime = min_vruntime(vruntime, se->vruntime);
	}

	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

295 296 297
/*
 * Enqueue an entity into the rb-tree:
 */
298
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
299 300 301 302
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
303
	s64 key = entity_key(cfs_rq, se);
304 305 306 307 308 309 310 311 312 313 314 315
	int leftmost = 1;

	/*
	 * Find the right place in the rbtree:
	 */
	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * We dont care about collisions. Nodes with
		 * the same key stay together.
		 */
316
		if (key < entity_key(cfs_rq, entry)) {
317 318 319 320 321 322 323 324 325 326 327
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

	/*
	 * Maintain a cache of leftmost tree entries (it is frequently
	 * used):
	 */
328
	if (leftmost)
I
Ingo Molnar 已提交
329
		cfs_rq->rb_leftmost = &se->run_node;
330 331 332 333 334

	rb_link_node(&se->run_node, parent, link);
	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

335
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
336
{
P
Peter Zijlstra 已提交
337 338 339 340 341 342
	if (cfs_rq->rb_leftmost == &se->run_node) {
		struct rb_node *next_node;

		next_node = rb_next(&se->run_node);
		cfs_rq->rb_leftmost = next_node;
	}
I
Ingo Molnar 已提交
343

344 345 346 347 348
	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
349 350 351 352 353 354
	struct rb_node *left = cfs_rq->rb_leftmost;

	if (!left)
		return NULL;

	return rb_entry(left, struct sched_entity, run_node);
355 356
}

357
static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
358
{
359
	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
360

361 362
	if (!last)
		return NULL;
363 364

	return rb_entry(last, struct sched_entity, run_node);
365 366
}

367 368 369 370
/**************************************************************
 * Scheduling class statistics methods:
 */

371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
#ifdef CONFIG_SCHED_DEBUG
int sched_nr_latency_handler(struct ctl_table *table, int write,
		struct file *filp, void __user *buffer, size_t *lenp,
		loff_t *ppos)
{
	int ret = proc_dointvec_minmax(table, write, filp, buffer, lenp, ppos);

	if (ret || !write)
		return ret;

	sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
					sysctl_sched_min_granularity);

	return 0;
}
#endif
387

388
/*
389
 * delta *= P[w / rw]
390 391 392 393 394 395 396 397 398 399 400 401 402
 */
static inline unsigned long
calc_delta_weight(unsigned long delta, struct sched_entity *se)
{
	for_each_sched_entity(se) {
		delta = calc_delta_mine(delta,
				se->load.weight, &cfs_rq_of(se)->load);
	}

	return delta;
}

/*
403
 * delta /= w
404 405 406 407
 */
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
408 409
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
410 411 412 413

	return delta;
}

414 415 416 417 418 419 420 421
/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
422 423 424
static u64 __sched_period(unsigned long nr_running)
{
	u64 period = sysctl_sched_latency;
425
	unsigned long nr_latency = sched_nr_latency;
426 427

	if (unlikely(nr_running > nr_latency)) {
428
		period = sysctl_sched_min_granularity;
429 430 431 432 433 434
		period *= nr_running;
	}

	return period;
}

435 436 437 438
/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
439
 * s = p*P[w/rw]
440
 */
P
Peter Zijlstra 已提交
441
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
442
{
443 444 445 446 447 448
	unsigned long nr_running = cfs_rq->nr_running;

	if (unlikely(!se->on_rq))
		nr_running++;

	return calc_delta_weight(__sched_period(nr_running), se);
449 450
}

451
/*
452
 * We calculate the vruntime slice of a to be inserted task
453
 *
454
 * vs = s/w
455
 */
456
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
P
Peter Zijlstra 已提交
457
{
458
	return calc_delta_fair(sched_slice(cfs_rq, se), se);
459 460
}

461 462 463 464 465
/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
static inline void
I
Ingo Molnar 已提交
466 467
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
	      unsigned long delta_exec)
468
{
469
	unsigned long delta_exec_weighted;
470

471
	schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
472 473

	curr->sum_exec_runtime += delta_exec;
474
	schedstat_add(cfs_rq, exec_clock, delta_exec);
475
	delta_exec_weighted = calc_delta_fair(delta_exec, curr);
I
Ingo Molnar 已提交
476
	curr->vruntime += delta_exec_weighted;
477
	update_min_vruntime(cfs_rq);
478 479
}

480
static void update_curr(struct cfs_rq *cfs_rq)
481
{
482
	struct sched_entity *curr = cfs_rq->curr;
I
Ingo Molnar 已提交
483
	u64 now = rq_of(cfs_rq)->clock;
484 485 486 487 488 489 490 491 492 493
	unsigned long delta_exec;

	if (unlikely(!curr))
		return;

	/*
	 * Get the amount of time the current task was running
	 * since the last time we changed load (this cannot
	 * overflow on 32 bits):
	 */
I
Ingo Molnar 已提交
494
	delta_exec = (unsigned long)(now - curr->exec_start);
495

I
Ingo Molnar 已提交
496 497
	__update_curr(cfs_rq, curr, delta_exec);
	curr->exec_start = now;
498 499 500 501 502

	if (entity_is_task(curr)) {
		struct task_struct *curtask = task_of(curr);

		cpuacct_charge(curtask, delta_exec);
503
		account_group_exec_runtime(curtask, delta_exec);
504
	}
505 506 507
}

static inline void
508
update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
509
{
510
	schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
511 512 513 514 515
}

/*
 * Task is being enqueued - update stats:
 */
516
static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
517 518 519 520 521
{
	/*
	 * Are we enqueueing a waiting task? (for current tasks
	 * a dequeue/enqueue event is a NOP)
	 */
522
	if (se != cfs_rq->curr)
523
		update_stats_wait_start(cfs_rq, se);
524 525 526
}

static void
527
update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
528
{
529 530
	schedstat_set(se->wait_max, max(se->wait_max,
			rq_of(cfs_rq)->clock - se->wait_start));
531 532 533
	schedstat_set(se->wait_count, se->wait_count + 1);
	schedstat_set(se->wait_sum, se->wait_sum +
			rq_of(cfs_rq)->clock - se->wait_start);
I
Ingo Molnar 已提交
534
	schedstat_set(se->wait_start, 0);
535 536 537
}

static inline void
538
update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
539 540 541 542 543
{
	/*
	 * Mark the end of the wait period if dequeueing a
	 * waiting task:
	 */
544
	if (se != cfs_rq->curr)
545
		update_stats_wait_end(cfs_rq, se);
546 547 548 549 550 551
}

/*
 * We are picking a new current task - update its stats:
 */
static inline void
552
update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
553 554 555 556
{
	/*
	 * We are starting a new run period:
	 */
557
	se->exec_start = rq_of(cfs_rq)->clock;
558 559 560 561 562 563
}

/**************************************************
 * Scheduling class queueing methods:
 */

564 565 566 567 568 569 570 571 572 573 574 575 576
#if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
static void
add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
{
	cfs_rq->task_weight += weight;
}
#else
static inline void
add_cfs_task_weight(struct cfs_rq *cfs_rq, unsigned long weight)
{
}
#endif

577 578 579 580
static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_add(&cfs_rq->load, se->load.weight);
581 582
	if (!parent_entity(se))
		inc_cpu_load(rq_of(cfs_rq), se->load.weight);
583
	if (entity_is_task(se)) {
584
		add_cfs_task_weight(cfs_rq, se->load.weight);
585 586
		list_add(&se->group_node, &cfs_rq->tasks);
	}
587 588 589 590 591 592 593 594
	cfs_rq->nr_running++;
	se->on_rq = 1;
}

static void
account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_sub(&cfs_rq->load, se->load.weight);
595 596
	if (!parent_entity(se))
		dec_cpu_load(rq_of(cfs_rq), se->load.weight);
597
	if (entity_is_task(se)) {
598
		add_cfs_task_weight(cfs_rq, -se->load.weight);
599 600
		list_del_init(&se->group_node);
	}
601 602 603 604
	cfs_rq->nr_running--;
	se->on_rq = 0;
}

605
static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
606 607 608
{
#ifdef CONFIG_SCHEDSTATS
	if (se->sleep_start) {
609
		u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
A
Arjan van de Ven 已提交
610
		struct task_struct *tsk = task_of(se);
611 612 613 614 615 616 617 618 619

		if ((s64)delta < 0)
			delta = 0;

		if (unlikely(delta > se->sleep_max))
			se->sleep_max = delta;

		se->sleep_start = 0;
		se->sum_sleep_runtime += delta;
A
Arjan van de Ven 已提交
620 621

		account_scheduler_latency(tsk, delta >> 10, 1);
622 623
	}
	if (se->block_start) {
624
		u64 delta = rq_of(cfs_rq)->clock - se->block_start;
A
Arjan van de Ven 已提交
625
		struct task_struct *tsk = task_of(se);
626 627 628 629 630 631 632 633 634

		if ((s64)delta < 0)
			delta = 0;

		if (unlikely(delta > se->block_max))
			se->block_max = delta;

		se->block_start = 0;
		se->sum_sleep_runtime += delta;
I
Ingo Molnar 已提交
635 636 637 638 639 640 641

		/*
		 * Blocking time is in units of nanosecs, so shift by 20 to
		 * get a milliseconds-range estimation of the amount of
		 * time that the task spent sleeping:
		 */
		if (unlikely(prof_on == SLEEP_PROFILING)) {
I
Ingo Molnar 已提交
642

I
Ingo Molnar 已提交
643 644 645
			profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
				     delta >> 20);
		}
A
Arjan van de Ven 已提交
646
		account_scheduler_latency(tsk, delta >> 10, 0);
647 648 649 650
	}
#endif
}

P
Peter Zijlstra 已提交
651 652 653 654 655 656 657 658 659 660 661 662 663
static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
#ifdef CONFIG_SCHED_DEBUG
	s64 d = se->vruntime - cfs_rq->min_vruntime;

	if (d < 0)
		d = -d;

	if (d > 3*sysctl_sched_latency)
		schedstat_inc(cfs_rq, nr_spread_over);
#endif
}

664 665 666
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
667
	u64 vruntime = cfs_rq->min_vruntime;
P
Peter Zijlstra 已提交
668

669 670 671 672 673 674
	/*
	 * The 'current' period is already promised to the current tasks,
	 * however the extra weight of the new task will slow them down a
	 * little, place the new task so that it fits in the slot that
	 * stays open at the end.
	 */
P
Peter Zijlstra 已提交
675
	if (initial && sched_feat(START_DEBIT))
676
		vruntime += sched_vslice(cfs_rq, se);
677

I
Ingo Molnar 已提交
678
	if (!initial) {
679
		/* sleeps upto a single latency don't count. */
680 681 682 683 684 685 686 687 688 689 690
		if (sched_feat(NEW_FAIR_SLEEPERS)) {
			unsigned long thresh = sysctl_sched_latency;

			/*
			 * convert the sleeper threshold into virtual time
			 */
			if (sched_feat(NORMALIZED_SLEEPER))
				thresh = calc_delta_fair(thresh, se);

			vruntime -= thresh;
		}
691

692 693
		/* ensure we never gain time by being placed backwards. */
		vruntime = max_vruntime(se->vruntime, vruntime);
694 695
	}

P
Peter Zijlstra 已提交
696
	se->vruntime = vruntime;
697 698
}

699
static void
700
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
701 702
{
	/*
703
	 * Update run-time statistics of the 'current'.
704
	 */
705
	update_curr(cfs_rq);
P
Peter Zijlstra 已提交
706
	account_entity_enqueue(cfs_rq, se);
707

I
Ingo Molnar 已提交
708
	if (wakeup) {
709
		place_entity(cfs_rq, se, 0);
710
		enqueue_sleeper(cfs_rq, se);
I
Ingo Molnar 已提交
711
	}
712

713
	update_stats_enqueue(cfs_rq, se);
P
Peter Zijlstra 已提交
714
	check_spread(cfs_rq, se);
715 716
	if (se != cfs_rq->curr)
		__enqueue_entity(cfs_rq, se);
717 718
}

P
Peter Zijlstra 已提交
719 720 721 722 723 724 725 726 727
static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (cfs_rq->last == se)
		cfs_rq->last = NULL;

	if (cfs_rq->next == se)
		cfs_rq->next = NULL;
}

728
static void
729
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
730
{
731 732 733 734 735
	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);

736
	update_stats_dequeue(cfs_rq, se);
737
	if (sleep) {
P
Peter Zijlstra 已提交
738
#ifdef CONFIG_SCHEDSTATS
739 740 741 742
		if (entity_is_task(se)) {
			struct task_struct *tsk = task_of(se);

			if (tsk->state & TASK_INTERRUPTIBLE)
743
				se->sleep_start = rq_of(cfs_rq)->clock;
744
			if (tsk->state & TASK_UNINTERRUPTIBLE)
745
				se->block_start = rq_of(cfs_rq)->clock;
746
		}
747
#endif
P
Peter Zijlstra 已提交
748 749
	}

P
Peter Zijlstra 已提交
750
	clear_buddies(cfs_rq, se);
P
Peter Zijlstra 已提交
751

752
	if (se != cfs_rq->curr)
753 754
		__dequeue_entity(cfs_rq, se);
	account_entity_dequeue(cfs_rq, se);
755
	update_min_vruntime(cfs_rq);
756 757 758 759 760
}

/*
 * Preempt the current task with a newly woken task if needed:
 */
761
static void
I
Ingo Molnar 已提交
762
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
763
{
764 765
	unsigned long ideal_runtime, delta_exec;

P
Peter Zijlstra 已提交
766
	ideal_runtime = sched_slice(cfs_rq, curr);
767
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
I
Ingo Molnar 已提交
768
	if (delta_exec > ideal_runtime)
769 770 771
		resched_task(rq_of(cfs_rq)->curr);
}

772
static void
773
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
774
{
775 776 777 778 779 780 781 782 783 784 785
	/* 'current' is not kept within the tree. */
	if (se->on_rq) {
		/*
		 * Any task has to be enqueued before it get to execute on
		 * a CPU. So account for the time it spent waiting on the
		 * runqueue.
		 */
		update_stats_wait_end(cfs_rq, se);
		__dequeue_entity(cfs_rq, se);
	}

786
	update_stats_curr_start(cfs_rq, se);
787
	cfs_rq->curr = se;
I
Ingo Molnar 已提交
788 789 790 791 792 793
#ifdef CONFIG_SCHEDSTATS
	/*
	 * Track our maximum slice length, if the CPU's load is at
	 * least twice that of our own weight (i.e. dont track it
	 * when there are only lesser-weight tasks around):
	 */
794
	if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
I
Ingo Molnar 已提交
795 796 797 798
		se->slice_max = max(se->slice_max,
			se->sum_exec_runtime - se->prev_sum_exec_runtime);
	}
#endif
799
	se->prev_sum_exec_runtime = se->sum_exec_runtime;
800 801
}

802 803 804
static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);

805
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
806
{
807 808
	struct sched_entity *se = __pick_next_entity(cfs_rq);

P
Peter Zijlstra 已提交
809 810
	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
		return cfs_rq->next;
811

P
Peter Zijlstra 已提交
812 813 814 815
	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
		return cfs_rq->last;

	return se;
816 817
}

818
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
819 820 821 822 823 824
{
	/*
	 * If still on the runqueue then deactivate_task()
	 * was not called and update_curr() has to be done:
	 */
	if (prev->on_rq)
825
		update_curr(cfs_rq);
826

P
Peter Zijlstra 已提交
827
	check_spread(cfs_rq, prev);
828
	if (prev->on_rq) {
829
		update_stats_wait_start(cfs_rq, prev);
830 831 832
		/* Put 'current' back into the tree. */
		__enqueue_entity(cfs_rq, prev);
	}
833
	cfs_rq->curr = NULL;
834 835
}

P
Peter Zijlstra 已提交
836 837
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
838 839
{
	/*
840
	 * Update run-time statistics of the 'current'.
841
	 */
842
	update_curr(cfs_rq);
843

P
Peter Zijlstra 已提交
844 845 846 847 848
#ifdef CONFIG_SCHED_HRTICK
	/*
	 * queued ticks are scheduled to match the slice, so don't bother
	 * validating it and just reschedule.
	 */
849 850 851 852
	if (queued) {
		resched_task(rq_of(cfs_rq)->curr);
		return;
	}
P
Peter Zijlstra 已提交
853 854 855 856 857 858 859 860
	/*
	 * don't let the period tick interfere with the hrtick preemption
	 */
	if (!sched_feat(DOUBLE_TICK) &&
			hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
		return;
#endif

861
	if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
I
Ingo Molnar 已提交
862
		check_preempt_tick(cfs_rq, curr);
863 864 865 866 867 868
}

/**************************************************
 * CFS operations on tasks:
 */

P
Peter Zijlstra 已提交
869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891
#ifdef CONFIG_SCHED_HRTICK
static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
{
	struct sched_entity *se = &p->se;
	struct cfs_rq *cfs_rq = cfs_rq_of(se);

	WARN_ON(task_rq(p) != rq);

	if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {
		u64 slice = sched_slice(cfs_rq, se);
		u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
		s64 delta = slice - ran;

		if (delta < 0) {
			if (rq->curr == p)
				resched_task(p);
			return;
		}

		/*
		 * Don't schedule slices shorter than 10000ns, that just
		 * doesn't make sense. Rely on vruntime for fairness.
		 */
892
		if (rq->curr != p)
893
			delta = max_t(s64, 10000LL, delta);
P
Peter Zijlstra 已提交
894

895
		hrtick_start(rq, delta);
P
Peter Zijlstra 已提交
896 897
	}
}
898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913

/*
 * called from enqueue/dequeue and updates the hrtick when the
 * current task is from our class and nr_running is low enough
 * to matter.
 */
static void hrtick_update(struct rq *rq)
{
	struct task_struct *curr = rq->curr;

	if (curr->sched_class != &fair_sched_class)
		return;

	if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
		hrtick_start_fair(rq, curr);
}
914
#else /* !CONFIG_SCHED_HRTICK */
P
Peter Zijlstra 已提交
915 916 917 918
static inline void
hrtick_start_fair(struct rq *rq, struct task_struct *p)
{
}
919 920 921 922

static inline void hrtick_update(struct rq *rq)
{
}
P
Peter Zijlstra 已提交
923 924
#endif

925 926 927 928 929
/*
 * The enqueue_task method is called before nr_running is
 * increased. Here we update the fair scheduling stats and
 * then put the task into the rbtree:
 */
930
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
931 932
{
	struct cfs_rq *cfs_rq;
933
	struct sched_entity *se = &p->se;
934 935

	for_each_sched_entity(se) {
936
		if (se->on_rq)
937 938
			break;
		cfs_rq = cfs_rq_of(se);
939
		enqueue_entity(cfs_rq, se, wakeup);
940
		wakeup = 1;
941
	}
P
Peter Zijlstra 已提交
942

943
	hrtick_update(rq);
944 945 946 947 948 949 950
}

/*
 * The dequeue_task method is called before nr_running is
 * decreased. We remove the task from the rbtree and
 * update the fair scheduling stats:
 */
951
static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
952 953
{
	struct cfs_rq *cfs_rq;
954
	struct sched_entity *se = &p->se;
955 956 957

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
958
		dequeue_entity(cfs_rq, se, sleep);
959
		/* Don't dequeue parent if it has other entities besides us */
960
		if (cfs_rq->load.weight)
961
			break;
962
		sleep = 1;
963
	}
P
Peter Zijlstra 已提交
964

965
	hrtick_update(rq);
966 967 968
}

/*
969 970 971
 * sched_yield() support is very simple - we dequeue and enqueue.
 *
 * If compat_yield is turned on then we requeue to the end of the tree.
972
 */
973
static void yield_task_fair(struct rq *rq)
974
{
975 976 977
	struct task_struct *curr = rq->curr;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
	struct sched_entity *rightmost, *se = &curr->se;
978 979

	/*
980 981 982 983 984
	 * Are we the only task in the tree?
	 */
	if (unlikely(cfs_rq->nr_running == 1))
		return;

P
Peter Zijlstra 已提交
985 986
	clear_buddies(cfs_rq, se);

987
	if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
988
		update_rq_clock(rq);
989
		/*
990
		 * Update run-time statistics of the 'current'.
991
		 */
D
Dmitry Adamushko 已提交
992
		update_curr(cfs_rq);
993 994 995 996 997

		return;
	}
	/*
	 * Find the rightmost entry in the rbtree:
998
	 */
D
Dmitry Adamushko 已提交
999
	rightmost = __pick_last_entity(cfs_rq);
1000 1001 1002
	/*
	 * Already in the rightmost position?
	 */
1003
	if (unlikely(!rightmost || rightmost->vruntime < se->vruntime))
1004 1005 1006 1007
		return;

	/*
	 * Minimally necessary key value to be last in the tree:
D
Dmitry Adamushko 已提交
1008 1009
	 * Upon rescheduling, sched_class::put_prev_task() will place
	 * 'current' within the tree based on its new key value.
1010
	 */
1011
	se->vruntime = rightmost->vruntime + 1;
1012 1013
}

1014 1015 1016 1017 1018
/*
 * wake_idle() will wake a task on an idle cpu if task->cpu is
 * not idle and an idle cpu is available.  The span of cpus to
 * search starts with cpus closest then further out as needed,
 * so we always favor a closer, idle cpu.
1019 1020
 * Domains may include CPUs that are not usable for migration,
 * hence we need to mask them out (cpu_active_map)
1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039
 *
 * Returns the CPU we should wake onto.
 */
#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
static int wake_idle(int cpu, struct task_struct *p)
{
	cpumask_t tmp;
	struct sched_domain *sd;
	int i;

	/*
	 * If it is idle, then it is the best cpu to run this task.
	 *
	 * This cpu is also the best, if it has more than one task already.
	 * Siblings must be also busy(in most cases) as they didn't already
	 * pickup the extra load from this cpu and hence we need not check
	 * sibling runqueue info. This will avoid the checks and cache miss
	 * penalities associated with that.
	 */
1040
	if (idle_cpu(cpu) || cpu_rq(cpu)->cfs.nr_running > 1)
1041 1042 1043
		return cpu;

	for_each_domain(cpu, sd) {
1044 1045 1046
		if ((sd->flags & SD_WAKE_IDLE)
		    || ((sd->flags & SD_WAKE_IDLE_FAR)
			&& !task_hot(p, task_rq(p)->clock, sd))) {
1047
			cpus_and(tmp, sd->span, p->cpus_allowed);
1048
			cpus_and(tmp, tmp, cpu_active_map);
1049
			for_each_cpu_mask_nr(i, tmp) {
1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063
				if (idle_cpu(i)) {
					if (i != task_cpu(p)) {
						schedstat_inc(p,
						       se.nr_wakeups_idle);
					}
					return i;
				}
			}
		} else {
			break;
		}
	}
	return cpu;
}
1064
#else /* !ARCH_HAS_SCHED_WAKE_IDLE*/
1065 1066 1067 1068 1069 1070 1071
static inline int wake_idle(int cpu, struct task_struct *p)
{
	return cpu;
}
#endif

#ifdef CONFIG_SMP
1072

1073
#ifdef CONFIG_FAIR_GROUP_SCHED
1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
/*
 * effective_load() calculates the load change as seen from the root_task_group
 *
 * Adding load to a group doesn't make a group heavier, but can cause movement
 * of group shares between cpus. Assuming the shares were perfectly aligned one
 * can calculate the shift in shares.
 *
 * The problem is that perfectly aligning the shares is rather expensive, hence
 * we try to avoid doing that too often - see update_shares(), which ratelimits
 * this change.
 *
 * We compensate this by not only taking the current delta into account, but
 * also considering the delta between when the shares were last adjusted and
 * now.
 *
 * We still saw a performance dip, some tracing learned us that between
 * cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased
 * significantly. Therefore try to bias the error in direction of failing
 * the affine wakeup.
 *
 */
1095 1096
static long effective_load(struct task_group *tg, int cpu,
		long wl, long wg)
1097
{
P
Peter Zijlstra 已提交
1098
	struct sched_entity *se = tg->se[cpu];
1099 1100 1101 1102

	if (!tg->parent)
		return wl;

1103 1104 1105 1106 1107 1108 1109
	/*
	 * By not taking the decrease of shares on the other cpu into
	 * account our error leans towards reducing the affine wakeups.
	 */
	if (!wl && sched_feat(ASYM_EFF_LOAD))
		return wl;

P
Peter Zijlstra 已提交
1110
	for_each_sched_entity(se) {
1111
		long S, rw, s, a, b;
1112 1113 1114 1115 1116 1117 1118 1119 1120
		long more_w;

		/*
		 * Instead of using this increment, also add the difference
		 * between when the shares were last updated and now.
		 */
		more_w = se->my_q->load.weight - se->my_q->rq_weight;
		wl += more_w;
		wg += more_w;
P
Peter Zijlstra 已提交
1121 1122 1123

		S = se->my_q->tg->shares;
		s = se->my_q->shares;
1124
		rw = se->my_q->rq_weight;
1125

1126 1127
		a = S*(rw + wl);
		b = S*rw + s*wg;
P
Peter Zijlstra 已提交
1128

1129 1130 1131 1132 1133
		wl = s*(a-b);

		if (likely(b))
			wl /= b;

1134 1135 1136 1137 1138 1139 1140
		/*
		 * Assume the group is already running and will
		 * thus already be accounted for in the weight.
		 *
		 * That is, moving shares between CPUs, does not
		 * alter the group weight.
		 */
P
Peter Zijlstra 已提交
1141 1142
		wg = 0;
	}
1143

P
Peter Zijlstra 已提交
1144
	return wl;
1145
}
P
Peter Zijlstra 已提交
1146

1147
#else
P
Peter Zijlstra 已提交
1148

1149 1150
static inline unsigned long effective_load(struct task_group *tg, int cpu,
		unsigned long wl, unsigned long wg)
P
Peter Zijlstra 已提交
1151
{
1152
	return wl;
1153
}
P
Peter Zijlstra 已提交
1154

1155 1156
#endif

1157
static int
1158
wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
I
Ingo Molnar 已提交
1159 1160
	    struct task_struct *p, int prev_cpu, int this_cpu, int sync,
	    int idx, unsigned long load, unsigned long this_load,
1161 1162
	    unsigned int imbalance)
{
I
Ingo Molnar 已提交
1163
	struct task_struct *curr = this_rq->curr;
1164
	struct task_group *tg;
1165 1166
	unsigned long tl = this_load;
	unsigned long tl_per_task;
1167
	unsigned long weight;
1168
	int balanced;
1169

1170
	if (!(this_sd->flags & SD_WAKE_AFFINE) || !sched_feat(AFFINE_WAKEUPS))
1171 1172
		return 0;

M
Mike Galbraith 已提交
1173 1174 1175
	if (sync && (curr->se.avg_overlap > sysctl_sched_migration_cost ||
			p->se.avg_overlap > sysctl_sched_migration_cost))
		sync = 0;
1176

1177 1178 1179 1180 1181
	/*
	 * If sync wakeup then subtract the (maximum possible)
	 * effect of the currently running task from the load
	 * of the current CPU:
	 */
1182 1183 1184 1185 1186 1187 1188
	if (sync) {
		tg = task_group(current);
		weight = current->se.load.weight;

		tl += effective_load(tg, this_cpu, -weight, -weight);
		load += effective_load(tg, prev_cpu, 0, -weight);
	}
1189

1190 1191
	tg = task_group(p);
	weight = p->se.load.weight;
1192

1193 1194
	balanced = 100*(tl + effective_load(tg, this_cpu, weight, weight)) <=
		imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
1195

1196
	/*
I
Ingo Molnar 已提交
1197 1198 1199
	 * If the currently running task will sleep within
	 * a reasonable amount of time then attract this newly
	 * woken task:
1200
	 */
1201 1202
	if (sync && balanced)
		return 1;
1203 1204 1205 1206

	schedstat_inc(p, se.nr_wakeups_affine_attempts);
	tl_per_task = cpu_avg_load_per_task(this_cpu);

1207 1208
	if (balanced || (tl <= load && tl + target_load(prev_cpu, idx) <=
			tl_per_task)) {
1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221
		/*
		 * This domain has SD_WAKE_AFFINE and
		 * p is cache cold in this domain, and
		 * there is no bad imbalance.
		 */
		schedstat_inc(this_sd, ttwu_move_affine);
		schedstat_inc(p, se.nr_wakeups_affine);

		return 1;
	}
	return 0;
}

1222 1223 1224
static int select_task_rq_fair(struct task_struct *p, int sync)
{
	struct sched_domain *sd, *this_sd = NULL;
1225
	int prev_cpu, this_cpu, new_cpu;
1226
	unsigned long load, this_load;
1227
	struct rq *this_rq;
1228 1229
	unsigned int imbalance;
	int idx;
1230

1231 1232
	prev_cpu	= task_cpu(p);
	this_cpu	= smp_processor_id();
I
Ingo Molnar 已提交
1233
	this_rq		= cpu_rq(this_cpu);
1234
	new_cpu		= prev_cpu;
1235

1236 1237
	if (prev_cpu == this_cpu)
		goto out;
1238 1239 1240 1241
	/*
	 * 'this_sd' is the first domain that both
	 * this_cpu and prev_cpu are present in:
	 */
1242
	for_each_domain(this_cpu, sd) {
1243
		if (cpu_isset(prev_cpu, sd->span)) {
1244 1245 1246 1247 1248 1249
			this_sd = sd;
			break;
		}
	}

	if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
1250
		goto out;
1251 1252 1253 1254

	/*
	 * Check for affine wakeup and passive balancing possibilities.
	 */
1255
	if (!this_sd)
1256
		goto out;
1257

1258 1259 1260 1261
	idx = this_sd->wake_idx;

	imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;

1262
	load = source_load(prev_cpu, idx);
1263 1264
	this_load = target_load(this_cpu, idx);

1265
	if (wake_affine(this_sd, this_rq, p, prev_cpu, this_cpu, sync, idx,
I
Ingo Molnar 已提交
1266 1267 1268
				     load, this_load, imbalance))
		return this_cpu;

1269 1270 1271 1272 1273 1274 1275 1276
	/*
	 * Start passive balancing when half the imbalance_pct
	 * limit is reached.
	 */
	if (this_sd->flags & SD_WAKE_BALANCE) {
		if (imbalance*this_load <= 100*load) {
			schedstat_inc(this_sd, ttwu_move_balance);
			schedstat_inc(p, se.nr_wakeups_passive);
I
Ingo Molnar 已提交
1277
			return this_cpu;
1278 1279 1280
		}
	}

1281
out:
1282 1283 1284 1285
	return wake_idle(new_cpu, p);
}
#endif /* CONFIG_SMP */

1286 1287 1288 1289 1290
static unsigned long wakeup_gran(struct sched_entity *se)
{
	unsigned long gran = sysctl_sched_wakeup_granularity;

	/*
1291 1292
	 * More easily preempt - nice tasks, while not making it harder for
	 * + nice tasks.
1293
	 */
1294 1295
	if (!sched_feat(ASYM_GRAN) || se->load.weight > NICE_0_LOAD)
		gran = calc_delta_fair(sysctl_sched_wakeup_granularity, se);
1296 1297 1298 1299

	return gran;
}

1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328
/*
 * Should 'se' preempt 'curr'.
 *
 *             |s1
 *        |s2
 *   |s3
 *         g
 *      |<--->|c
 *
 *  w(c, s1) = -1
 *  w(c, s2) =  0
 *  w(c, s3) =  1
 *
 */
static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
	s64 gran, vdiff = curr->vruntime - se->vruntime;

	if (vdiff <= 0)
		return -1;

	gran = wakeup_gran(curr);
	if (vdiff > gran)
		return 1;

	return 0;
}

1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340
static void set_last_buddy(struct sched_entity *se)
{
	for_each_sched_entity(se)
		cfs_rq_of(se)->last = se;
}

static void set_next_buddy(struct sched_entity *se)
{
	for_each_sched_entity(se)
		cfs_rq_of(se)->next = se;
}

1341 1342 1343
/*
 * Preempt the current task with a newly woken task if needed:
 */
1344
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
1345 1346
{
	struct task_struct *curr = rq->curr;
1347
	struct sched_entity *se = &curr->se, *pse = &p->se;
1348 1349

	if (unlikely(rt_prio(p->prio))) {
P
Peter Zijlstra 已提交
1350 1351
		struct cfs_rq *cfs_rq = task_cfs_rq(curr);

I
Ingo Molnar 已提交
1352
		update_rq_clock(rq);
1353
		update_curr(cfs_rq);
1354 1355 1356
		resched_task(curr);
		return;
	}
1357

P
Peter Zijlstra 已提交
1358 1359 1360
	if (unlikely(p->sched_class != &fair_sched_class))
		return;

I
Ingo Molnar 已提交
1361 1362 1363
	if (unlikely(se == pse))
		return;

P
Peter Zijlstra 已提交
1364 1365 1366 1367 1368 1369 1370 1371 1372 1373
	/*
	 * Only set the backward buddy when the current task is still on the
	 * rq. This can happen when a wakeup gets interleaved with schedule on
	 * the ->pre_schedule() or idle_balance() point, either of which can
	 * drop the rq lock.
	 *
	 * Also, during early boot the idle thread is in the fair class, for
	 * obvious reasons its a bad idea to schedule back to the idle thread.
	 */
	if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))
1374 1375
		set_last_buddy(se);
	set_next_buddy(pse);
P
Peter Zijlstra 已提交
1376

1377 1378 1379 1380 1381 1382 1383
	/*
	 * We can come here with TIF_NEED_RESCHED already set from new task
	 * wake up path.
	 */
	if (test_tsk_need_resched(curr))
		return;

1384 1385 1386 1387 1388 1389
	/*
	 * Batch tasks do not preempt (their preemption is driven by
	 * the tick):
	 */
	if (unlikely(p->policy == SCHED_BATCH))
		return;
1390

1391 1392
	if (!sched_feat(WAKEUP_PREEMPT))
		return;
1393

1394 1395 1396
	if (sched_feat(WAKEUP_OVERLAP) && (sync ||
			(se->avg_overlap < sysctl_sched_migration_cost &&
			 pse->avg_overlap < sysctl_sched_migration_cost))) {
1397 1398 1399 1400
		resched_task(curr);
		return;
	}

1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413
	find_matching_se(&se, &pse);

	while (se) {
		BUG_ON(!pse);

		if (wakeup_preempt_entity(se, pse) == 1) {
			resched_task(curr);
			break;
		}

		se = parent_entity(se);
		pse = parent_entity(pse);
	}
1414 1415
}

1416
static struct task_struct *pick_next_task_fair(struct rq *rq)
1417
{
P
Peter Zijlstra 已提交
1418
	struct task_struct *p;
1419 1420 1421 1422 1423 1424 1425
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;

	if (unlikely(!cfs_rq->nr_running))
		return NULL;

	do {
1426
		se = pick_next_entity(cfs_rq);
1427
		set_next_entity(cfs_rq, se);
1428 1429 1430
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

P
Peter Zijlstra 已提交
1431 1432 1433 1434
	p = task_of(se);
	hrtick_start_fair(rq, p);

	return p;
1435 1436 1437 1438 1439
}

/*
 * Account for a descheduled task:
 */
1440
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
1441 1442 1443 1444 1445 1446
{
	struct sched_entity *se = &prev->se;
	struct cfs_rq *cfs_rq;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
1447
		put_prev_entity(cfs_rq, se);
1448 1449 1450
	}
}

1451
#ifdef CONFIG_SMP
1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462
/**************************************************
 * Fair scheduling class load-balancing methods:
 */

/*
 * Load-balancing iterator. Note: while the runqueue stays locked
 * during the whole iteration, the current task might be
 * dequeued so the iterator has to be dequeue-safe. Here we
 * achieve that by always pre-iterating before returning
 * the current task:
 */
A
Alexey Dobriyan 已提交
1463
static struct task_struct *
1464
__load_balance_iterator(struct cfs_rq *cfs_rq, struct list_head *next)
1465
{
D
Dhaval Giani 已提交
1466 1467
	struct task_struct *p = NULL;
	struct sched_entity *se;
1468

1469 1470 1471
	if (next == &cfs_rq->tasks)
		return NULL;

1472 1473 1474
	se = list_entry(next, struct sched_entity, group_node);
	p = task_of(se);
	cfs_rq->balance_iterator = next->next;
1475

1476 1477 1478 1479 1480 1481 1482
	return p;
}

static struct task_struct *load_balance_start_fair(void *arg)
{
	struct cfs_rq *cfs_rq = arg;

1483
	return __load_balance_iterator(cfs_rq, cfs_rq->tasks.next);
1484 1485 1486 1487 1488 1489
}

static struct task_struct *load_balance_next_fair(void *arg)
{
	struct cfs_rq *cfs_rq = arg;

1490
	return __load_balance_iterator(cfs_rq, cfs_rq->balance_iterator);
1491 1492
}

1493 1494 1495 1496 1497
static unsigned long
__load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
		unsigned long max_load_move, struct sched_domain *sd,
		enum cpu_idle_type idle, int *all_pinned, int *this_best_prio,
		struct cfs_rq *cfs_rq)
1498
{
1499
	struct rq_iterator cfs_rq_iterator;
1500

1501 1502 1503
	cfs_rq_iterator.start = load_balance_start_fair;
	cfs_rq_iterator.next = load_balance_next_fair;
	cfs_rq_iterator.arg = cfs_rq;
1504

1505 1506 1507
	return balance_tasks(this_rq, this_cpu, busiest,
			max_load_move, sd, idle, all_pinned,
			this_best_prio, &cfs_rq_iterator);
1508 1509
}

1510
#ifdef CONFIG_FAIR_GROUP_SCHED
P
Peter Williams 已提交
1511
static unsigned long
1512
load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1513
		  unsigned long max_load_move,
1514 1515
		  struct sched_domain *sd, enum cpu_idle_type idle,
		  int *all_pinned, int *this_best_prio)
1516 1517
{
	long rem_load_move = max_load_move;
1518 1519
	int busiest_cpu = cpu_of(busiest);
	struct task_group *tg;
1520

1521
	rcu_read_lock();
1522
	update_h_load(busiest_cpu);
1523

1524
	list_for_each_entry_rcu(tg, &task_groups, list) {
1525
		struct cfs_rq *busiest_cfs_rq = tg->cfs_rq[busiest_cpu];
1526 1527
		unsigned long busiest_h_load = busiest_cfs_rq->h_load;
		unsigned long busiest_weight = busiest_cfs_rq->load.weight;
S
Srivatsa Vaddagiri 已提交
1528
		u64 rem_load, moved_load;
1529

1530 1531 1532
		/*
		 * empty group
		 */
1533
		if (!busiest_cfs_rq->task_weight)
1534 1535
			continue;

S
Srivatsa Vaddagiri 已提交
1536 1537
		rem_load = (u64)rem_load_move * busiest_weight;
		rem_load = div_u64(rem_load, busiest_h_load + 1);
1538

1539
		moved_load = __load_balance_fair(this_rq, this_cpu, busiest,
1540
				rem_load, sd, idle, all_pinned, this_best_prio,
1541
				tg->cfs_rq[busiest_cpu]);
1542

1543
		if (!moved_load)
1544 1545
			continue;

1546
		moved_load *= busiest_h_load;
S
Srivatsa Vaddagiri 已提交
1547
		moved_load = div_u64(moved_load, busiest_weight + 1);
1548

1549 1550
		rem_load_move -= moved_load;
		if (rem_load_move < 0)
1551 1552
			break;
	}
1553
	rcu_read_unlock();
1554

P
Peter Williams 已提交
1555
	return max_load_move - rem_load_move;
1556
}
1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568
#else
static unsigned long
load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
		  unsigned long max_load_move,
		  struct sched_domain *sd, enum cpu_idle_type idle,
		  int *all_pinned, int *this_best_prio)
{
	return __load_balance_fair(this_rq, this_cpu, busiest,
			max_load_move, sd, idle, all_pinned,
			this_best_prio, &busiest->cfs);
}
#endif
1569

1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592
static int
move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
		   struct sched_domain *sd, enum cpu_idle_type idle)
{
	struct cfs_rq *busy_cfs_rq;
	struct rq_iterator cfs_rq_iterator;

	cfs_rq_iterator.start = load_balance_start_fair;
	cfs_rq_iterator.next = load_balance_next_fair;

	for_each_leaf_cfs_rq(busiest, busy_cfs_rq) {
		/*
		 * pass busy_cfs_rq argument into
		 * load_balance_[start|next]_fair iterators
		 */
		cfs_rq_iterator.arg = busy_cfs_rq;
		if (iter_move_one_task(this_rq, this_cpu, busiest, sd, idle,
				       &cfs_rq_iterator))
		    return 1;
	}

	return 0;
}
1593
#endif /* CONFIG_SMP */
1594

1595 1596 1597
/*
 * scheduler tick hitting a task of our scheduling class:
 */
P
Peter Zijlstra 已提交
1598
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
1599 1600 1601 1602 1603 1604
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &curr->se;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
P
Peter Zijlstra 已提交
1605
		entity_tick(cfs_rq, se, queued);
1606 1607 1608
	}
}

1609
#define swap(a, b) do { typeof(a) tmp = (a); (a) = (b); (b) = tmp; } while (0)
1610

1611 1612 1613 1614 1615 1616 1617
/*
 * Share the fairness runtime between parent and child, thus the
 * total amount of pressure for CPU stays equal - new tasks
 * get a chance to run but frequent forkers are not allowed to
 * monopolize the CPU. Note: the parent runqueue is locked,
 * the child is not running yet.
 */
1618
static void task_new_fair(struct rq *rq, struct task_struct *p)
1619 1620
{
	struct cfs_rq *cfs_rq = task_cfs_rq(p);
1621
	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
1622
	int this_cpu = smp_processor_id();
1623 1624 1625

	sched_info_queued(p);

1626
	update_curr(cfs_rq);
1627
	place_entity(cfs_rq, se, 1);
1628

1629
	/* 'curr' will be NULL if the child belongs to a different group */
1630
	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
1631
			curr && curr->vruntime < se->vruntime) {
D
Dmitry Adamushko 已提交
1632
		/*
1633 1634 1635
		 * Upon rescheduling, sched_class::put_prev_task() will place
		 * 'current' within the tree based on its new key value.
		 */
1636
		swap(curr->vruntime, se->vruntime);
1637
		resched_task(rq->curr);
1638
	}
1639

1640
	enqueue_task_fair(rq, p, 0);
1641 1642
}

1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658
/*
 * Priority of the task has changed. Check to see if we preempt
 * the current task.
 */
static void prio_changed_fair(struct rq *rq, struct task_struct *p,
			      int oldprio, int running)
{
	/*
	 * Reschedule if we are currently running on this runqueue and
	 * our priority decreased, or if we are not currently running on
	 * this runqueue and our priority is higher than the current's
	 */
	if (running) {
		if (p->prio > oldprio)
			resched_task(rq->curr);
	} else
1659
		check_preempt_curr(rq, p, 0);
1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675
}

/*
 * We switched to the sched_fair class.
 */
static void switched_to_fair(struct rq *rq, struct task_struct *p,
			     int running)
{
	/*
	 * We were most likely switched from sched_rt, so
	 * kick off the schedule if running, otherwise just see
	 * if we can still preempt the current task.
	 */
	if (running)
		resched_task(rq->curr);
	else
1676
		check_preempt_curr(rq, p, 0);
1677 1678
}

1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691
/* Account for a task changing its policy or group.
 *
 * This routine is mostly called to set cfs_rq->curr field when a task
 * migrates between groups/classes.
 */
static void set_curr_task_fair(struct rq *rq)
{
	struct sched_entity *se = &rq->curr->se;

	for_each_sched_entity(se)
		set_next_entity(cfs_rq_of(se), se);
}

P
Peter Zijlstra 已提交
1692 1693 1694 1695 1696 1697 1698 1699 1700 1701
#ifdef CONFIG_FAIR_GROUP_SCHED
static void moved_group_fair(struct task_struct *p)
{
	struct cfs_rq *cfs_rq = task_cfs_rq(p);

	update_curr(cfs_rq);
	place_entity(cfs_rq, &p->se, 1);
}
#endif

1702 1703 1704
/*
 * All the scheduling class methods:
 */
1705 1706
static const struct sched_class fair_sched_class = {
	.next			= &idle_sched_class,
1707 1708 1709 1710
	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task		= yield_task_fair,

I
Ingo Molnar 已提交
1711
	.check_preempt_curr	= check_preempt_wakeup,
1712 1713 1714 1715

	.pick_next_task		= pick_next_task_fair,
	.put_prev_task		= put_prev_task_fair,

1716
#ifdef CONFIG_SMP
L
Li Zefan 已提交
1717 1718
	.select_task_rq		= select_task_rq_fair,

1719
	.load_balance		= load_balance_fair,
1720
	.move_one_task		= move_one_task_fair,
1721
#endif
1722

1723
	.set_curr_task          = set_curr_task_fair,
1724 1725
	.task_tick		= task_tick_fair,
	.task_new		= task_new_fair,
1726 1727 1728

	.prio_changed		= prio_changed_fair,
	.switched_to		= switched_to_fair,
P
Peter Zijlstra 已提交
1729 1730 1731 1732

#ifdef CONFIG_FAIR_GROUP_SCHED
	.moved_group		= moved_group_fair,
#endif
1733 1734 1735
};

#ifdef CONFIG_SCHED_DEBUG
1736
static void print_cfs_stats(struct seq_file *m, int cpu)
1737 1738 1739
{
	struct cfs_rq *cfs_rq;

1740
	rcu_read_lock();
1741
	for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
1742
		print_cfs_rq(m, cpu, cfs_rq);
1743
	rcu_read_unlock();
1744 1745
}
#endif