sched_fair.c 34.7 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_BATCH wake-up granularity.
66
 * (default: 10 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.
 */
I
Ingo Molnar 已提交
72
unsigned int sysctl_sched_batch_wakeup_granularity = 10000000UL;
73 74 75

/*
 * SCHED_OTHER wake-up granularity.
76
 * (default: 10 msec * (1 + ilog(ncpus)), units: nanoseconds)
77 78 79 80 81
 *
 * This option delays the preemption effects of decoupled workloads
 * and reduces their over-scheduling. Synchronous workloads will still
 * have immediate wakeup/sleep latencies.
 */
I
Ingo Molnar 已提交
82
unsigned int sysctl_sched_wakeup_granularity = 10000000UL;
83

84 85
const_debug unsigned int sysctl_sched_migration_cost = 500000UL;

86 87 88 89
/**************************************************************
 * CFS operations on generic schedulable entities:
 */

90
#ifdef CONFIG_FAIR_GROUP_SCHED
91

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

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

101
#else	/* CONFIG_FAIR_GROUP_SCHED */
102

103 104 105
static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
{
	return container_of(cfs_rq, struct rq, cfs);
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
}

#define entity_is_task(se)	1

#endif	/* CONFIG_FAIR_GROUP_SCHED */

static inline struct task_struct *task_of(struct sched_entity *se)
{
	return container_of(se, struct task_struct, se);
}


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

122
static inline u64 max_vruntime(u64 min_vruntime, u64 vruntime)
123
{
124 125
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta > 0)
126 127 128 129 130
		min_vruntime = vruntime;

	return min_vruntime;
}

131
static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
P
Peter Zijlstra 已提交
132 133 134 135 136 137 138 139
{
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta < 0)
		min_vruntime = vruntime;

	return min_vruntime;
}

140
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
141
{
142
	return se->vruntime - cfs_rq->min_vruntime;
143 144
}

145 146 147
/*
 * Enqueue an entity into the rb-tree:
 */
148
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
149 150 151 152
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
153
	s64 key = entity_key(cfs_rq, se);
154 155 156 157 158 159 160 161 162 163 164 165
	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.
		 */
166
		if (key < entity_key(cfs_rq, entry)) {
167 168 169 170 171 172 173 174 175 176 177 178
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

	/*
	 * Maintain a cache of leftmost tree entries (it is frequently
	 * used):
	 */
	if (leftmost)
I
Ingo Molnar 已提交
179
		cfs_rq->rb_leftmost = &se->run_node;
180 181 182 183 184

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

185
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
186 187
{
	if (cfs_rq->rb_leftmost == &se->run_node)
I
Ingo Molnar 已提交
188
		cfs_rq->rb_leftmost = rb_next(&se->run_node);
I
Ingo Molnar 已提交
189

190 191 192 193 194 195 196 197 198 199 200 201 202
	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
{
	return cfs_rq->rb_leftmost;
}

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
	return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
}

203 204
static inline struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
{
205
	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
206

207 208
	if (!last)
		return NULL;
209 210

	return rb_entry(last, struct sched_entity, run_node);
211 212
}

213 214 215 216
/**************************************************************
 * Scheduling class statistics methods:
 */

217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
#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
233 234 235 236 237 238 239 240 241

/*
 * 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
 */
242 243 244
static u64 __sched_period(unsigned long nr_running)
{
	u64 period = sysctl_sched_latency;
245
	unsigned long nr_latency = sched_nr_latency;
246 247

	if (unlikely(nr_running > nr_latency)) {
248
		period = sysctl_sched_min_granularity;
249 250 251 252 253 254
		period *= nr_running;
	}

	return period;
}

255 256 257 258 259 260
/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*w/rw
 */
P
Peter Zijlstra 已提交
261
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
262
{
263
	u64 slice = __sched_period(cfs_rq->nr_running);
264

265 266
	slice *= se->load.weight;
	do_div(slice, cfs_rq->load.weight);
267

268
	return slice;
269 270
}

271 272 273 274 275 276
/*
 * We calculate the vruntime slice.
 *
 * vs = s/w = p/rw
 */
static u64 __sched_vslice(unsigned long rq_weight, unsigned long nr_running)
P
Peter Zijlstra 已提交
277
{
278
	u64 vslice = __sched_period(nr_running);
P
Peter Zijlstra 已提交
279

P
Peter Zijlstra 已提交
280
	vslice *= NICE_0_LOAD;
281
	do_div(vslice, rq_weight);
P
Peter Zijlstra 已提交
282

283 284
	return vslice;
}
285

286 287 288 289 290 291 292 293 294
static u64 sched_vslice(struct cfs_rq *cfs_rq)
{
	return __sched_vslice(cfs_rq->load.weight, cfs_rq->nr_running);
}

static u64 sched_vslice_add(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return __sched_vslice(cfs_rq->load.weight + se->load.weight,
			cfs_rq->nr_running + 1);
P
Peter Zijlstra 已提交
295 296
}

297 298 299 300 301
/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
static inline void
I
Ingo Molnar 已提交
302 303
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
	      unsigned long delta_exec)
304
{
305
	unsigned long delta_exec_weighted;
P
Peter Zijlstra 已提交
306
	u64 vruntime;
307

308
	schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
309 310

	curr->sum_exec_runtime += delta_exec;
311
	schedstat_add(cfs_rq, exec_clock, delta_exec);
I
Ingo Molnar 已提交
312 313 314 315 316 317
	delta_exec_weighted = delta_exec;
	if (unlikely(curr->load.weight != NICE_0_LOAD)) {
		delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
							&curr->load);
	}
	curr->vruntime += delta_exec_weighted;
318 319 320 321 322 323

	/*
	 * maintain cfs_rq->min_vruntime to be a monotonic increasing
	 * value tracking the leftmost vruntime in the tree.
	 */
	if (first_fair(cfs_rq)) {
P
Peter Zijlstra 已提交
324 325
		vruntime = min_vruntime(curr->vruntime,
				__pick_next_entity(cfs_rq)->vruntime);
326
	} else
P
Peter Zijlstra 已提交
327
		vruntime = curr->vruntime;
328 329

	cfs_rq->min_vruntime =
P
Peter Zijlstra 已提交
330
		max_vruntime(cfs_rq->min_vruntime, vruntime);
331 332
}

333
static void update_curr(struct cfs_rq *cfs_rq)
334
{
335
	struct sched_entity *curr = cfs_rq->curr;
I
Ingo Molnar 已提交
336
	u64 now = rq_of(cfs_rq)->clock;
337 338 339 340 341 342 343 344 345 346
	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 已提交
347
	delta_exec = (unsigned long)(now - curr->exec_start);
348

I
Ingo Molnar 已提交
349 350
	__update_curr(cfs_rq, curr, delta_exec);
	curr->exec_start = now;
351 352 353 354 355 356

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

		cpuacct_charge(curtask, delta_exec);
	}
357 358 359
}

static inline void
360
update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
361
{
362
	schedstat_set(se->wait_start, rq_of(cfs_rq)->clock);
363 364 365 366 367
}

/*
 * Task is being enqueued - update stats:
 */
368
static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
369 370 371 372 373
{
	/*
	 * Are we enqueueing a waiting task? (for current tasks
	 * a dequeue/enqueue event is a NOP)
	 */
374
	if (se != cfs_rq->curr)
375
		update_stats_wait_start(cfs_rq, se);
376 377 378
}

static void
379
update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
380
{
381 382
	schedstat_set(se->wait_max, max(se->wait_max,
			rq_of(cfs_rq)->clock - se->wait_start));
383 384 385
	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 已提交
386
	schedstat_set(se->wait_start, 0);
387 388 389
}

static inline void
390
update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
391 392 393 394 395
{
	/*
	 * Mark the end of the wait period if dequeueing a
	 * waiting task:
	 */
396
	if (se != cfs_rq->curr)
397
		update_stats_wait_end(cfs_rq, se);
398 399 400 401 402 403
}

/*
 * We are picking a new current task - update its stats:
 */
static inline void
404
update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
405 406 407 408
{
	/*
	 * We are starting a new run period:
	 */
409
	se->exec_start = rq_of(cfs_rq)->clock;
410 411 412 413 414 415
}

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

416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_add(&cfs_rq->load, se->load.weight);
	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);
	cfs_rq->nr_running--;
	se->on_rq = 0;
}

432
static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
433 434 435
{
#ifdef CONFIG_SCHEDSTATS
	if (se->sleep_start) {
436
		u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
A
Arjan van de Ven 已提交
437
		struct task_struct *tsk = task_of(se);
438 439 440 441 442 443 444 445 446

		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 已提交
447 448

		account_scheduler_latency(tsk, delta >> 10, 1);
449 450
	}
	if (se->block_start) {
451
		u64 delta = rq_of(cfs_rq)->clock - se->block_start;
A
Arjan van de Ven 已提交
452
		struct task_struct *tsk = task_of(se);
453 454 455 456 457 458 459 460 461

		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 已提交
462 463 464 465 466 467 468

		/*
		 * 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 已提交
469

I
Ingo Molnar 已提交
470 471 472
			profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
				     delta >> 20);
		}
A
Arjan van de Ven 已提交
473
		account_scheduler_latency(tsk, delta >> 10, 0);
474 475 476 477
	}
#endif
}

P
Peter Zijlstra 已提交
478 479 480 481 482 483 484 485 486 487 488 489 490
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
}

491 492 493
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
P
Peter Zijlstra 已提交
494
	u64 vruntime;
495

P
Peter Zijlstra 已提交
496
	vruntime = cfs_rq->min_vruntime;
P
Peter Zijlstra 已提交
497

498
	if (sched_feat(TREE_AVG)) {
P
Peter Zijlstra 已提交
499 500
		struct sched_entity *last = __pick_last_entity(cfs_rq);
		if (last) {
P
Peter Zijlstra 已提交
501 502
			vruntime += last->vruntime;
			vruntime >>= 1;
P
Peter Zijlstra 已提交
503
		}
P
Peter Zijlstra 已提交
504
	} else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
505
		vruntime += sched_vslice(cfs_rq)/2;
P
Peter Zijlstra 已提交
506

507 508 509 510 511 512
	/*
	 * 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 已提交
513
	if (initial && sched_feat(START_DEBIT))
514
		vruntime += sched_vslice_add(cfs_rq, se);
515

I
Ingo Molnar 已提交
516
	if (!initial) {
517
		/* sleeps upto a single latency don't count. */
518
		if (sched_feat(NEW_FAIR_SLEEPERS))
519 520
			vruntime -= sysctl_sched_latency;

521 522
		/* ensure we never gain time by being placed backwards. */
		vruntime = max_vruntime(se->vruntime, vruntime);
523 524
	}

P
Peter Zijlstra 已提交
525
	se->vruntime = vruntime;
526 527
}

528
static void
529
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
530 531
{
	/*
532
	 * Update run-time statistics of the 'current'.
533
	 */
534
	update_curr(cfs_rq);
535

I
Ingo Molnar 已提交
536
	if (wakeup) {
537
		place_entity(cfs_rq, se, 0);
538
		enqueue_sleeper(cfs_rq, se);
I
Ingo Molnar 已提交
539
	}
540

541
	update_stats_enqueue(cfs_rq, se);
P
Peter Zijlstra 已提交
542
	check_spread(cfs_rq, se);
543 544
	if (se != cfs_rq->curr)
		__enqueue_entity(cfs_rq, se);
545
	account_entity_enqueue(cfs_rq, se);
546 547 548
}

static void
549
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
550
{
551 552 553 554 555
	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);

556
	update_stats_dequeue(cfs_rq, se);
557
	if (sleep) {
P
Peter Zijlstra 已提交
558
#ifdef CONFIG_SCHEDSTATS
559 560 561 562
		if (entity_is_task(se)) {
			struct task_struct *tsk = task_of(se);

			if (tsk->state & TASK_INTERRUPTIBLE)
563
				se->sleep_start = rq_of(cfs_rq)->clock;
564
			if (tsk->state & TASK_UNINTERRUPTIBLE)
565
				se->block_start = rq_of(cfs_rq)->clock;
566
		}
567
#endif
P
Peter Zijlstra 已提交
568 569
	}

570
	if (se != cfs_rq->curr)
571 572
		__dequeue_entity(cfs_rq, se);
	account_entity_dequeue(cfs_rq, se);
573 574 575 576 577
}

/*
 * Preempt the current task with a newly woken task if needed:
 */
578
static void
I
Ingo Molnar 已提交
579
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
580
{
581 582
	unsigned long ideal_runtime, delta_exec;

P
Peter Zijlstra 已提交
583
	ideal_runtime = sched_slice(cfs_rq, curr);
584
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
I
Ingo Molnar 已提交
585
	if (delta_exec > ideal_runtime)
586 587 588
		resched_task(rq_of(cfs_rq)->curr);
}

589
static void
590
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
591
{
592 593 594 595 596 597 598 599 600 601 602
	/* '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);
	}

603
	update_stats_curr_start(cfs_rq, se);
604
	cfs_rq->curr = se;
I
Ingo Molnar 已提交
605 606 607 608 609 610
#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):
	 */
611
	if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
I
Ingo Molnar 已提交
612 613 614 615
		se->slice_max = max(se->slice_max,
			se->sum_exec_runtime - se->prev_sum_exec_runtime);
	}
#endif
616
	se->prev_sum_exec_runtime = se->sum_exec_runtime;
617 618
}

619
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
620
{
D
Dmitry Adamushko 已提交
621
	struct sched_entity *se = NULL;
622

D
Dmitry Adamushko 已提交
623 624 625 626
	if (first_fair(cfs_rq)) {
		se = __pick_next_entity(cfs_rq);
		set_next_entity(cfs_rq, se);
	}
627 628 629 630

	return se;
}

631
static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
632 633 634 635 636 637
{
	/*
	 * If still on the runqueue then deactivate_task()
	 * was not called and update_curr() has to be done:
	 */
	if (prev->on_rq)
638
		update_curr(cfs_rq);
639

P
Peter Zijlstra 已提交
640
	check_spread(cfs_rq, prev);
641
	if (prev->on_rq) {
642
		update_stats_wait_start(cfs_rq, prev);
643 644 645
		/* Put 'current' back into the tree. */
		__enqueue_entity(cfs_rq, prev);
	}
646
	cfs_rq->curr = NULL;
647 648
}

P
Peter Zijlstra 已提交
649 650
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
651 652
{
	/*
653
	 * Update run-time statistics of the 'current'.
654
	 */
655
	update_curr(cfs_rq);
656

P
Peter Zijlstra 已提交
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671
#ifdef CONFIG_SCHED_HRTICK
	/*
	 * queued ticks are scheduled to match the slice, so don't bother
	 * validating it and just reschedule.
	 */
	if (queued)
		return resched_task(rq_of(cfs_rq)->curr);
	/*
	 * 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

672
	if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
I
Ingo Molnar 已提交
673
		check_preempt_tick(cfs_rq, curr);
674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707
}

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

#ifdef CONFIG_FAIR_GROUP_SCHED

/* 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)
{
S
Srivatsa Vaddagiri 已提交
708
	return cfs_rq->tg->cfs_rq[this_cpu];
709 710 711 712
}

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

715 716 717
/* Do the two (enqueued) entities belong to the same group ? */
static inline int
is_same_group(struct sched_entity *se, struct sched_entity *pse)
718
{
719
	if (se->cfs_rq == pse->cfs_rq)
720 721 722 723 724
		return 1;

	return 0;
}

725 726 727 728 729
static inline struct sched_entity *parent_entity(struct sched_entity *se)
{
	return se->parent;
}

730 731
#define GROUP_IMBALANCE_PCT	20

732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763
#else	/* CONFIG_FAIR_GROUP_SCHED */

#define for_each_sched_entity(se) \
		for (; se; se = NULL)

static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
{
	return &task_rq(p)->cfs;
}

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)

764 765
static inline int
is_same_group(struct sched_entity *se, struct sched_entity *pse)
766 767 768 769
{
	return 1;
}

770 771 772 773 774
static inline struct sched_entity *parent_entity(struct sched_entity *se)
{
	return NULL;
}

775 776
#endif	/* CONFIG_FAIR_GROUP_SCHED */

P
Peter Zijlstra 已提交
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813
#ifdef CONFIG_SCHED_HRTICK
static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
{
	int requeue = rq->curr == 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.
		 */
		if (!requeue)
			delta = max(10000LL, delta);

		hrtick_start(rq, delta, requeue);
	}
}
#else
static inline void
hrtick_start_fair(struct rq *rq, struct task_struct *p)
{
}
#endif

814 815 816 817 818
/*
 * 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:
 */
819
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
820 821
{
	struct cfs_rq *cfs_rq;
822 823 824
	struct sched_entity *se = &p->se,
			    *topse = NULL;	/* Highest schedulable entity */
	int incload = 1;
825 826

	for_each_sched_entity(se) {
827 828 829
		topse = se;
		if (se->on_rq) {
			incload = 0;
830
			break;
831
		}
832
		cfs_rq = cfs_rq_of(se);
833
		enqueue_entity(cfs_rq, se, wakeup);
834
		wakeup = 1;
835
	}
836 837 838 839 840 841
	/* Increment cpu load if we just enqueued the first task of a group on
	 * 'rq->cpu'. 'topse' represents the group to which task 'p' belongs
	 * at the highest grouping level.
	 */
	if (incload)
		inc_cpu_load(rq, topse->load.weight);
P
Peter Zijlstra 已提交
842 843

	hrtick_start_fair(rq, rq->curr);
844 845 846 847 848 849 850
}

/*
 * The dequeue_task method is called before nr_running is
 * decreased. We remove the task from the rbtree and
 * update the fair scheduling stats:
 */
851
static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
852 853
{
	struct cfs_rq *cfs_rq;
854 855 856
	struct sched_entity *se = &p->se,
			    *topse = NULL; 	/* Highest schedulable entity */
	int decload = 1;
857 858

	for_each_sched_entity(se) {
859
		topse = se;
860
		cfs_rq = cfs_rq_of(se);
861
		dequeue_entity(cfs_rq, se, sleep);
862
		/* Don't dequeue parent if it has other entities besides us */
863 864 865
		if (cfs_rq->load.weight) {
			if (parent_entity(se))
				decload = 0;
866
			break;
867
		}
868
		sleep = 1;
869
	}
870 871 872 873 874 875
	/* Decrement cpu load if we just dequeued the last task of a group on
	 * 'rq->cpu'. 'topse' represents the group to which task 'p' belongs
	 * at the highest grouping level.
	 */
	if (decload)
		dec_cpu_load(rq, topse->load.weight);
P
Peter Zijlstra 已提交
876 877

	hrtick_start_fair(rq, rq->curr);
878 879 880
}

/*
881 882 883
 * 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.
884
 */
885
static void yield_task_fair(struct rq *rq)
886
{
887 888 889
	struct task_struct *curr = rq->curr;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
	struct sched_entity *rightmost, *se = &curr->se;
890 891

	/*
892 893 894 895 896
	 * Are we the only task in the tree?
	 */
	if (unlikely(cfs_rq->nr_running == 1))
		return;

897
	if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
898 899
		__update_rq_clock(rq);
		/*
900
		 * Update run-time statistics of the 'current'.
901
		 */
D
Dmitry Adamushko 已提交
902
		update_curr(cfs_rq);
903 904 905 906 907

		return;
	}
	/*
	 * Find the rightmost entry in the rbtree:
908
	 */
D
Dmitry Adamushko 已提交
909
	rightmost = __pick_last_entity(cfs_rq);
910 911 912
	/*
	 * Already in the rightmost position?
	 */
D
Dmitry Adamushko 已提交
913
	if (unlikely(rightmost->vruntime < se->vruntime))
914 915 916 917
		return;

	/*
	 * Minimally necessary key value to be last in the tree:
D
Dmitry Adamushko 已提交
918 919
	 * Upon rescheduling, sched_class::put_prev_task() will place
	 * 'current' within the tree based on its new key value.
920
	 */
921
	se->vruntime = rightmost->vruntime + 1;
922 923
}

924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988
/*
 * 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.
 *
 * 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.
	 */
	if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1)
		return cpu;

	for_each_domain(cpu, sd) {
		if (sd->flags & SD_WAKE_IDLE) {
			cpus_and(tmp, sd->span, p->cpus_allowed);
			for_each_cpu_mask(i, tmp) {
				if (idle_cpu(i)) {
					if (i != task_cpu(p)) {
						schedstat_inc(p,
						       se.nr_wakeups_idle);
					}
					return i;
				}
			}
		} else {
			break;
		}
	}
	return cpu;
}
#else
static inline int wake_idle(int cpu, struct task_struct *p)
{
	return cpu;
}
#endif

#ifdef CONFIG_SMP
static int select_task_rq_fair(struct task_struct *p, int sync)
{
	int cpu, this_cpu;
	struct rq *rq;
	struct sched_domain *sd, *this_sd = NULL;
	int new_cpu;

	cpu      = task_cpu(p);
	rq       = task_rq(p);
	this_cpu = smp_processor_id();
	new_cpu  = cpu;

989 990 991
	if (cpu == this_cpu)
		goto out_set_cpu;

992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071
	for_each_domain(this_cpu, sd) {
		if (cpu_isset(cpu, sd->span)) {
			this_sd = sd;
			break;
		}
	}

	if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed)))
		goto out_set_cpu;

	/*
	 * Check for affine wakeup and passive balancing possibilities.
	 */
	if (this_sd) {
		int idx = this_sd->wake_idx;
		unsigned int imbalance;
		unsigned long load, this_load;

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

		load = source_load(cpu, idx);
		this_load = target_load(this_cpu, idx);

		new_cpu = this_cpu; /* Wake to this CPU if we can */

		if (this_sd->flags & SD_WAKE_AFFINE) {
			unsigned long tl = this_load;
			unsigned long tl_per_task;

			/*
			 * Attract cache-cold tasks on sync wakeups:
			 */
			if (sync && !task_hot(p, rq->clock, this_sd))
				goto out_set_cpu;

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

			/*
			 * If sync wakeup then subtract the (maximum possible)
			 * effect of the currently running task from the load
			 * of the current CPU:
			 */
			if (sync)
				tl -= current->se.load.weight;

			if ((tl <= load &&
				tl + target_load(cpu, idx) <= tl_per_task) ||
			       100*(tl + p->se.load.weight) <= imbalance*load) {
				/*
				 * 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);
				goto out_set_cpu;
			}
		}

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

	new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */
out_set_cpu:
	return wake_idle(new_cpu, p);
}
#endif /* CONFIG_SMP */


1072 1073 1074
/*
 * Preempt the current task with a newly woken task if needed:
 */
I
Ingo Molnar 已提交
1075
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
1076 1077
{
	struct task_struct *curr = rq->curr;
1078
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
1079
	struct sched_entity *se = &curr->se, *pse = &p->se;
1080
	unsigned long gran;
1081 1082

	if (unlikely(rt_prio(p->prio))) {
I
Ingo Molnar 已提交
1083
		update_rq_clock(rq);
1084
		update_curr(cfs_rq);
1085 1086 1087
		resched_task(curr);
		return;
	}
1088 1089 1090 1091 1092 1093
	/*
	 * Batch tasks do not preempt (their preemption is driven by
	 * the tick):
	 */
	if (unlikely(p->policy == SCHED_BATCH))
		return;
1094

1095 1096
	if (!sched_feat(WAKEUP_PREEMPT))
		return;
1097

1098 1099 1100
	while (!is_same_group(se, pse)) {
		se = parent_entity(se);
		pse = parent_entity(pse);
1101
	}
1102 1103

	gran = sysctl_sched_wakeup_granularity;
1104 1105 1106 1107 1108
	/*
	 * More easily preempt - nice tasks, while not making
	 * it harder for + nice tasks.
	 */
	if (unlikely(se->load.weight > NICE_0_LOAD))
1109 1110
		gran = calc_delta_fair(gran, &se->load);

1111
	if (pse->vruntime + gran < se->vruntime)
1112
		resched_task(curr);
1113 1114
}

1115
static struct task_struct *pick_next_task_fair(struct rq *rq)
1116
{
P
Peter Zijlstra 已提交
1117
	struct task_struct *p;
1118 1119 1120 1121 1122 1123 1124
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;

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

	do {
1125
		se = pick_next_entity(cfs_rq);
1126 1127 1128
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

P
Peter Zijlstra 已提交
1129 1130 1131 1132
	p = task_of(se);
	hrtick_start_fair(rq, p);

	return p;
1133 1134 1135 1136 1137
}

/*
 * Account for a descheduled task:
 */
1138
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
1139 1140 1141 1142 1143 1144
{
	struct sched_entity *se = &prev->se;
	struct cfs_rq *cfs_rq;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
1145
		put_prev_entity(cfs_rq, se);
1146 1147 1148
	}
}

1149
#ifdef CONFIG_SMP
1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160
/**************************************************
 * 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 已提交
1161
static struct task_struct *
1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188
__load_balance_iterator(struct cfs_rq *cfs_rq, struct rb_node *curr)
{
	struct task_struct *p;

	if (!curr)
		return NULL;

	p = rb_entry(curr, struct task_struct, se.run_node);
	cfs_rq->rb_load_balance_curr = rb_next(curr);

	return p;
}

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

	return __load_balance_iterator(cfs_rq, first_fair(cfs_rq));
}

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

	return __load_balance_iterator(cfs_rq, cfs_rq->rb_load_balance_curr);
}

P
Peter Williams 已提交
1189
static unsigned long
1190
load_balance_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
1191
		  unsigned long max_load_move,
1192 1193
		  struct sched_domain *sd, enum cpu_idle_type idle,
		  int *all_pinned, int *this_best_prio)
1194 1195 1196 1197
{
	struct cfs_rq *busy_cfs_rq;
	long rem_load_move = max_load_move;
	struct rq_iterator cfs_rq_iterator;
1198
	unsigned long load_moved;
1199 1200 1201 1202 1203

	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) {
1204
#ifdef CONFIG_FAIR_GROUP_SCHED
1205 1206 1207 1208
		struct cfs_rq *this_cfs_rq = busy_cfs_rq->tg->cfs_rq[this_cpu];
		unsigned long maxload, task_load, group_weight;
		unsigned long thisload, per_task_load;
		struct sched_entity *se = busy_cfs_rq->tg->se[busiest->cpu];
1209

1210 1211
		task_load = busy_cfs_rq->load.weight;
		group_weight = se->load.weight;
1212

1213 1214 1215 1216 1217 1218 1219 1220 1221 1222
		/*
		 * 'group_weight' is contributed by tasks of total weight
		 * 'task_load'. To move 'rem_load_move' worth of weight only,
		 * we need to move a maximum task load of:
		 *
		 * 	maxload = (remload / group_weight) * task_load;
		 */
		maxload = (rem_load_move * task_load) / group_weight;

		if (!maxload || !task_load)
1223 1224
			continue;

1225 1226 1227 1228 1229 1230 1231 1232
		per_task_load = task_load / busy_cfs_rq->nr_running;
		/*
		 * balance_tasks will try to forcibly move atleast one task if
		 * possible (because of SCHED_LOAD_SCALE_FUZZ). Avoid that if
		 * maxload is less than GROUP_IMBALANCE_FUZZ% the per_task_load.
		 */
		 if (100 * maxload < GROUP_IMBALANCE_PCT * per_task_load)
			continue;
1233

1234 1235 1236
		/* Disable priority-based load balance */
		*this_best_prio = 0;
		thisload = this_cfs_rq->load.weight;
1237
#else
1238
# define maxload rem_load_move
1239
#endif
1240 1241
		/*
		 * pass busy_cfs_rq argument into
1242 1243 1244
		 * load_balance_[start|next]_fair iterators
		 */
		cfs_rq_iterator.arg = busy_cfs_rq;
1245
		load_moved = balance_tasks(this_rq, this_cpu, busiest,
1246 1247 1248
					       maxload, sd, idle, all_pinned,
					       this_best_prio,
					       &cfs_rq_iterator);
1249

1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
#ifdef CONFIG_FAIR_GROUP_SCHED
		/*
		 * load_moved holds the task load that was moved. The
		 * effective (group) weight moved would be:
		 * 	load_moved_eff = load_moved/task_load * group_weight;
		 */
		load_moved = (group_weight * load_moved) / task_load;

		/* Adjust shares on both cpus to reflect load_moved */
		group_weight -= load_moved;
		set_se_shares(se, group_weight);

		se = busy_cfs_rq->tg->se[this_cpu];
		if (!thisload)
			group_weight = load_moved;
		else
			group_weight = se->load.weight + load_moved;
		set_se_shares(se, group_weight);
#endif

		rem_load_move -= load_moved;

1272
		if (rem_load_move <= 0)
1273 1274 1275
			break;
	}

P
Peter Williams 已提交
1276
	return max_load_move - rem_load_move;
1277 1278
}

1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301
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;
}
1302
#endif
1303

1304 1305 1306
/*
 * scheduler tick hitting a task of our scheduling class:
 */
P
Peter Zijlstra 已提交
1307
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
1308 1309 1310 1311 1312 1313
{
	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 已提交
1314
		entity_tick(cfs_rq, se, queued);
1315 1316 1317
	}
}

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

1320 1321 1322 1323 1324 1325 1326
/*
 * 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.
 */
1327
static void task_new_fair(struct rq *rq, struct task_struct *p)
1328 1329
{
	struct cfs_rq *cfs_rq = task_cfs_rq(p);
1330
	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
1331
	int this_cpu = smp_processor_id();
1332 1333 1334

	sched_info_queued(p);

1335
	update_curr(cfs_rq);
1336
	place_entity(cfs_rq, se, 1);
1337

1338
	/* 'curr' will be NULL if the child belongs to a different group */
1339
	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
1340
			curr && curr->vruntime < se->vruntime) {
D
Dmitry Adamushko 已提交
1341
		/*
1342 1343 1344
		 * Upon rescheduling, sched_class::put_prev_task() will place
		 * 'current' within the tree based on its new key value.
		 */
1345 1346
		swap(curr->vruntime, se->vruntime);
	}
1347

1348
	enqueue_task_fair(rq, p, 0);
1349
	resched_task(rq->curr);
1350 1351
}

1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387
/*
 * 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
		check_preempt_curr(rq, p);
}

/*
 * 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
		check_preempt_curr(rq, p);
}

1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400
/* 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);
}

1401 1402 1403
/*
 * All the scheduling class methods:
 */
1404 1405
static const struct sched_class fair_sched_class = {
	.next			= &idle_sched_class,
1406 1407 1408
	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task		= yield_task_fair,
1409 1410 1411
#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_fair,
#endif /* CONFIG_SMP */
1412

I
Ingo Molnar 已提交
1413
	.check_preempt_curr	= check_preempt_wakeup,
1414 1415 1416 1417

	.pick_next_task		= pick_next_task_fair,
	.put_prev_task		= put_prev_task_fair,

1418
#ifdef CONFIG_SMP
1419
	.load_balance		= load_balance_fair,
1420
	.move_one_task		= move_one_task_fair,
1421
#endif
1422

1423
	.set_curr_task          = set_curr_task_fair,
1424 1425
	.task_tick		= task_tick_fair,
	.task_new		= task_new_fair,
1426 1427 1428

	.prio_changed		= prio_changed_fair,
	.switched_to		= switched_to_fair,
1429 1430 1431
};

#ifdef CONFIG_SCHED_DEBUG
1432
static void print_cfs_stats(struct seq_file *m, int cpu)
1433 1434 1435
{
	struct cfs_rq *cfs_rq;

S
Srivatsa Vaddagiri 已提交
1436 1437 1438
#ifdef CONFIG_FAIR_GROUP_SCHED
	print_cfs_rq(m, cpu, &cpu_rq(cpu)->cfs);
#endif
1439
	rcu_read_lock();
1440
	for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
1441
		print_cfs_rq(m, cpu, cfs_rq);
1442
	rcu_read_unlock();
1443 1444
}
#endif