Release 4.15 kernel/sched/fair.c

// SPDX-License-Identifier: GPL-2.0
/*
 * 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>
 *
 *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
 *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
 */

#include <linux/sched/mm.h>
#include <linux/sched/topology.h>

#include <linux/latencytop.h>
#include <linux/cpumask.h>
#include <linux/cpuidle.h>
#include <linux/slab.h>
#include <linux/profile.h>
#include <linux/interrupt.h>
#include <linux/mempolicy.h>
#include <linux/migrate.h>
#include <linux/task_work.h>
#include <linux/sched/isolation.h>

#include <trace/events/sched.h>

#include "sched.h"

/*
 * Targeted preemption latency for CPU-bound tasks:
 *
 * NOTE: this latency value is not the same as the concept of
 * 'timeslice length' - timeslices in CFS are of variable length
 * and have no persistent notion like in traditional, time-slice
 * based scheduling concepts.
 *
 * (to see the precise effective timeslice length of your workload,
 *  run vmstat and monitor the context-switches (cs) field)
 *
 * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
 */

unsigned int sysctl_sched_latency			= 6000000ULL;

unsigned int normalized_sysctl_sched_latency		= 6000000ULL;

/*
 * The initial- and re-scaling of tunables is configurable
 *
 * Options are:
 *
 *   SCHED_TUNABLESCALING_NONE - unscaled, always *1
 *   SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
 *   SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
 *
 * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
 */

enum sched_tunable_scaling sysctl_sched_tunable_scaling = SCHED_TUNABLESCALING_LOG;

/*
 * Minimal preemption granularity for CPU-bound tasks:
 *
 * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
 */

unsigned int sysctl_sched_min_granularity		= 750000ULL;

unsigned int normalized_sysctl_sched_min_granularity	= 750000ULL;

/*
 * This value is kept at sysctl_sched_latency/sysctl_sched_min_granularity
 */

static unsigned int sched_nr_latency = 8;

/*
 * After fork, child runs first. If set to 0 (default) then
 * parent will (try to) run first.
 */

unsigned int sysctl_sched_child_runs_first __read_mostly;

/*
 * SCHED_OTHER wake-up granularity.
 *
 * This option delays the preemption effects of decoupled workloads
 * and reduces their over-scheduling. Synchronous workloads will still
 * have immediate wakeup/sleep latencies.
 *
 * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
 */

unsigned int sysctl_sched_wakeup_granularity		= 1000000UL;

unsigned int normalized_sysctl_sched_wakeup_granularity	= 1000000UL;


const_debug unsigned int sysctl_sched_migration_cost	= 500000UL;

#ifdef CONFIG_SMP
/*
 * For asym packing, by default the lower numbered cpu has higher priority.
 */


int __weak arch_asym_cpu_priority(int cpu)
{
	return -cpu;
}
Contributors
Person
Tokens
Prop
Commits
CommitProp
Tim Chen
13
100.00%
1
100.00%
Total
13
100.00%
1
100.00%

#endif

#ifdef CONFIG_CFS_BANDWIDTH
/*
 * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
 * each time a cfs_rq requests quota.
 *
 * Note: in the case that the slice exceeds the runtime remaining (either due
 * to consumption or the quota being specified to be smaller than the slice)
 * we will always only issue the remaining available time.
 *
 * (default: 5 msec, units: microseconds)
 */

unsigned int sysctl_sched_cfs_bandwidth_slice		= 5000UL;
#endif

/*
 * The margin used when comparing utilization with CPU capacity:
 * util * margin < capacity * 1024
 *
 * (default: ~20%)
 */

unsigned int capacity_margin				= 1280;



static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
	lw->weight += inc;
	lw->inv_weight = 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Paul Gortmaker
28
100.00%
1
100.00%
Total
28
100.00%
1
100.00%



static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
{
	lw->weight -= dec;
	lw->inv_weight = 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Paul Gortmaker
28
100.00%
1
100.00%
Total
28
100.00%
1
100.00%



static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
	lw->weight = w;
	lw->inv_weight = 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Paul Gortmaker
28
100.00%
1
100.00%
Total
28
100.00%
1
100.00%

/*
 * Increase the granularity value when there are more CPUs,
 * because with more CPUs the 'effective latency' as visible
 * to users decreases. But the relationship is not linear,
 * so pick a second-best guess by going with the log2 of the
 * number of CPUs.
 *
 * This idea comes from the SD scheduler of Con Kolivas:
 */


static unsigned int get_update_sysctl_factor(void)
{
	unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
	unsigned int factor;

	switch (sysctl_sched_tunable_scaling) {
	case SCHED_TUNABLESCALING_NONE:
		factor = 1;
		break;
	case SCHED_TUNABLESCALING_LINEAR:
		factor = cpus;
		break;
	case SCHED_TUNABLESCALING_LOG:
	default:
		factor = 1 + ilog2(cpus);
		break;
	}

	return factor;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
55
84.62%
1
33.33%
Ingo Molnar
7
10.77%
1
33.33%
Nicholas Mc Guire
3
4.62%
1
33.33%
Total
65
100.00%
3
100.00%



static void update_sysctl(void)
{
	unsigned int factor = get_update_sysctl_factor();


#define SET_SYSCTL(name) \
	(sysctl_##name = (factor) * normalized_sysctl_##name)
	SET_SYSCTL(sched_min_granularity);
	SET_SYSCTL(sched_latency);
	SET_SYSCTL(sched_wakeup_granularity);

#undef SET_SYSCTL
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
41
100.00%
2
100.00%
Total
41
100.00%
2
100.00%



void sched_init_granularity(void)
{
	update_sysctl();
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
10
100.00%
2
100.00%
Total
10
100.00%
2
100.00%


#define WMULT_CONST	(~0U)

#define WMULT_SHIFT	32



static void __update_inv_weight(struct load_weight *lw)
{
	unsigned long w;

	if (likely(lw->inv_weight))
		return;

	w = scale_load_down(lw->weight);

	if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
		lw->inv_weight = 1;
	else if (unlikely(!w))
		lw->inv_weight = WMULT_CONST;
	else
		lw->inv_weight = WMULT_CONST / w;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
71
92.21%
3
75.00%
Ingo Molnar
6
7.79%
1
25.00%
Total
77
100.00%
4
100.00%

/*
 * delta_exec * weight / lw.weight
 *   OR
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
 * we're guaranteed shift stays positive because inv_weight is guaranteed to
 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
 *
 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
 * weight/lw.weight <= 1, and therefore our shift will also be positive.
 */


static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);
	int shift = WMULT_SHIFT;

	__update_inv_weight(lw);

	if (unlikely(fact >> 32)) {
		while (fact >> 32) {
			fact >>= 1;
			shift--;
		}
	}

	/* hint to use a 32x32->64 mul */
	fact = (u64)(u32)fact * lw->inv_weight;

	while (fact >> 32) {
		fact >>= 1;
		shift--;
	}

	return mul_u64_u32_shr(delta_exec, fact, shift);
}


Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
100
98.04%
2
66.67%
Ingo Molnar
2
1.96%
1
33.33%
Total
102
100.00%
3
100.00%


const struct sched_class fair_sched_class;

/**************************************************************
 * CFS operations on generic schedulable entities:
 */

#ifdef CONFIG_FAIR_GROUP_SCHED

/* cpu runqueue to which this cfs_rq is attached */


static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
{
	return cfs_rq->rq;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Ingo Molnar
12
63.16%
1
33.33%
Peter Zijlstra
7
36.84%
2
66.67%
Total
19
100.00%
3
100.00%

/* An entity is a task if it doesn't "own" a runqueue */

#define entity_is_task(se)	(!se->my_q)



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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
32
94.12%
4
80.00%
Ingo Molnar
2
5.88%
1
20.00%
Total
34
100.00%
5
100.00%

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
21
100.00%
2
100.00%
Total
21
100.00%
2
100.00%

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
19
100.00%
1
100.00%
Total
19
100.00%
1
100.00%

/* runqueue "owned" by this group */


static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
	return grp->my_q;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
19
100.00%
1
100.00%
Total
19
100.00%
1
100.00%



static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
{
	if (!cfs_rq->on_list) {
		struct rq *rq = rq_of(cfs_rq);
		int cpu = cpu_of(rq);
		/*
                 * Ensure we either appear before our parent (if already
                 * enqueued) or force our parent to appear after us when it is
                 * enqueued. The fact that we always enqueue bottom-up
                 * reduces this to two cases and a special case for the root
                 * cfs_rq. Furthermore, it also means that we will always reset
                 * tmp_alone_branch either when the branch is connected
                 * to a tree or when we reach the beg of the tree
                 */
		if (cfs_rq->tg->parent &&
		    cfs_rq->tg->parent->cfs_rq[cpu]->on_list) {
			/*
                         * If parent is already on the list, we add the child
                         * just before. Thanks to circular linked property of
                         * the list, this means to put the child at the tail
                         * of the list that starts by parent.
                         */
			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
				&(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list));
			/*
                         * The branch is now connected to its tree so we can
                         * reset tmp_alone_branch to the beginning of the
                         * list.
                         */
			rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
		} else if (!cfs_rq->tg->parent) {
			/*
                         * cfs rq without parent should be put
                         * at the tail of the list.
                         */
			list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
				&rq->leaf_cfs_rq_list);
			/*
                         * We have reach the beg of a tree so we can reset
                         * tmp_alone_branch to the beginning of the list.
                         */
			rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
		} else {
			/*
                         * The parent has not already been added so we want to
                         * make sure that it will be put after us.
                         * tmp_alone_branch points to the beg of the branch
                         * where we will add parent.
                         */
			list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
				rq->tmp_alone_branch);
			/*
                         * update tmp_alone_branch to points to the new beg
                         * of the branch
                         */
			rq->tmp_alone_branch = &cfs_rq->leaf_cfs_rq_list;
		}

		cfs_rq->on_list = 1;
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Vincent Guittot
89
53.61%
1
25.00%
Peter Zijlstra
39
23.49%
2
50.00%
Paul Turner
38
22.89%
1
25.00%
Total
166
100.00%
4
100.00%



static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
{
	if (cfs_rq->on_list) {
		list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
		cfs_rq->on_list = 0;
	}
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
34
100.00%
1
100.00%
Total
34
100.00%
1
100.00%

/* Iterate thr' all leaf cfs_rq's on a runqueue */

#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)			\
	list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list,    \
                                 leaf_cfs_rq_list)

/* Do the two (enqueued) entities belong to the same group ? */

static inline struct cfs_rq *

is_same_group(struct sched_entity *se, struct sched_entity *pse)
{
	if (se->cfs_rq == pse->cfs_rq)
		return se->cfs_rq;

	return NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
21
56.76%
3
75.00%
Ingo Molnar
16
43.24%
1
25.00%
Total
37
100.00%
4
100.00%



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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
11
57.89%
2
66.67%
Ingo Molnar
8
42.11%
1
33.33%
Total
19
100.00%
3
100.00%


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 = (*se)->depth;
	pse_depth = (*pse)->depth;

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
115
100.00%
2
100.00%
Total
115
100.00%
2
100.00%

#else	/* !CONFIG_FAIR_GROUP_SCHED */



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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
25
100.00%
1
100.00%
Total
25
100.00%
1
100.00%



static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
{
	return container_of(cfs_rq, struct rq, cfs);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Ingo Molnar
15
60.00%
1
50.00%
Peter Zijlstra
10
40.00%
1
50.00%
Total
25
100.00%
2
100.00%


#define entity_is_task(se)	1


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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Ingo Molnar
13
56.52%
1
50.00%
Peter Zijlstra
10
43.48%
1
50.00%
Total
23
100.00%
2
100.00%



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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
36
90.00%
2
50.00%
Balbir Singh
2
5.00%
1
25.00%
Ingo Molnar
2
5.00%
1
25.00%
Total
40
100.00%
4
100.00%

/* runqueue "owned" by this group */


static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
	return NULL;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
17
100.00%
1
100.00%
Total
17
100.00%
1
100.00%



static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
{
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
11
100.00%
1
100.00%
Total
11
100.00%
1
100.00%



static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
{
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
11
100.00%
1
100.00%
Total
11
100.00%
1
100.00%


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



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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
17
100.00%
2
100.00%
Total
17
100.00%
2
100.00%


static inline void

find_matching_se(struct sched_entity **se, struct sched_entity **pse)
{
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
18
100.00%
1
100.00%
Total
18
100.00%
1
100.00%

#endif	/* CONFIG_FAIR_GROUP_SCHED */

static __always_inline
void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);

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



static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
{
	s64 delta = (s64)(vruntime - max_vruntime);
	if (delta > 0)
		max_vruntime = vruntime;

	return max_vruntime;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
34
89.47%
3
75.00%
Andrei Epure
4
10.53%
1
25.00%
Total
38
100.00%
4
100.00%



static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
{
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta < 0)
		min_vruntime = vruntime;

	return min_vruntime;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
34
89.47%
5
83.33%
Ingo Molnar
4
10.53%
1
16.67%
Total
38
100.00%
6
100.00%



static inline int entity_before(struct sched_entity *a,
				struct sched_entity *b)
{
	return (s64)(a->vruntime - b->vruntime) < 0;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Fabio Checconi
33
100.00%
1
100.00%
Total
33
100.00%
1
100.00%



static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);

	u64 vruntime = cfs_rq->min_vruntime;

	if (curr) {
		if (curr->on_rq)
			vruntime = curr->vruntime;
		else
			curr = NULL;
	}

	if (leftmost) { /* non-empty tree */
		struct sched_entity *se;
		se = rb_entry(leftmost, struct sched_entity, run_node);

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

	/* ensure we never gain time by being placed backwards. */
	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
	smp_wmb();
	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
119
85.00%
4
66.67%
Davidlohr Bueso A
20
14.29%
1
16.67%
Andrei Epure
1
0.71%
1
16.67%
Total
140
100.00%
6
100.00%

/*
 * Enqueue an entity into the rb-tree:
 */


static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	bool leftmost = true;

	/*
         * 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.
                 */
		if (entity_before(se, entry)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
95
71.43%
1
14.29%
Ingo Molnar
28
21.05%
4
57.14%
Davidlohr Bueso A
8
6.02%
1
14.29%
Stephan Bärwolf
2
1.50%
1
14.29%
Total
133
100.00%
7
100.00%



static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
13
44.83%
1
25.00%
Ingo Molnar
10
34.48%
1
25.00%
Srivatsa Vaddagiri
5
17.24%
1
25.00%
Davidlohr Bueso A
1
3.45%
1
25.00%
Total
29
100.00%
4
100.00%



struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);

	if (!left)
		return NULL;

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
30
68.18%
2
33.33%
Ingo Molnar
8
18.18%
2
33.33%
Davidlohr Bueso A
5
11.36%
1
16.67%
Rik Van Riel
1
2.27%
1
16.67%
Total
44
100.00%
6
100.00%



static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{
	struct rb_node *next = rb_next(&se->run_node);

	if (!next)
		return NULL;

	return rb_entry(next, struct sched_entity, run_node);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Rik Van Riel
45
100.00%
1
100.00%
Total
45
100.00%
1
100.00%

#ifdef CONFIG_SCHED_DEBUG


struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *last = rb_last(&cfs_rq->tasks_timeline.rb_root);

	if (!last)
		return NULL;

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

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
30
65.22%
1
25.00%
Ingo Molnar
14
30.43%
2
50.00%
Davidlohr Bueso A
2
4.35%
1
25.00%
Total
46
100.00%
4
100.00%

/**************************************************************
 * Scheduling class statistics methods:
 */



int sched_proc_update_handler(struct ctl_table *table, int write,
		void __user *buffer, size_t *lenp,
		loff_t *ppos)
{
	int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
	unsigned int factor = get_update_sysctl_factor();

	if (ret || !write)
		return ret;

	sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
					sysctl_sched_min_granularity);


#define WRT_SYSCTL(name) \
	(normalized_sysctl_##name = sysctl_##name / (factor))
	WRT_SYSCTL(sched_min_granularity);
	WRT_SYSCTL(sched_latency);
	WRT_SYSCTL(sched_wakeup_granularity);

#undef WRT_SYSCTL

	return 0;
}
Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
49
50.52%
1
12.50%
Christian Ehrhardt
33
34.02%
1
12.50%
Ingo Molnar
11
11.34%
4
50.00%
Arjan van de Ven
3
3.09%
1
12.50%
Nicholas Mc Guire
1
1.03%
1
12.50%
Total
97
100.00%
8
100.00%

#endif

/*
 * delta /= w
 */


static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

	return delta;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
45
100.00%
3
100.00%
Total
45
100.00%
3
100.00%

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */


static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity;
	else
		return sysctl_sched_latency;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
19
67.86%
1
33.33%
Boqun Feng
7
25.00%
1
33.33%
Arjan van de Ven
2
7.14%
1
33.33%
Total
28
100.00%
3
100.00%

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */


static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

	for_each_sched_entity(se) {
		struct load_weight *load;
		struct load_weight lw;

		cfs_rq = cfs_rq_of(se);
		load = &cfs_rq->load;

		if (unlikely(!se->on_rq)) {
			lw = cfs_rq->load;

			update_load_add(&lw, se->load.weight);
			load = &lw;
		}
		slice = __calc_delta(slice, se->load.weight, load);
	}
	return slice;
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Mike Galbraith
59
52.21%
1
11.11%
Peter Zijlstra
20
17.70%
4
44.44%
Ingo Molnar
17
15.04%
2
22.22%
Lin Ming
11
9.73%
1
11.11%
Christian Engelmayer
6
5.31%
1
11.11%
Total
113
100.00%
9
100.00%

/*
 * We calculate the vruntime slice of a to-be-inserted task.
 *
 * vs = s/w
 */


static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
25
86.21%
4
66.67%
Ingo Molnar
4
13.79%
2
33.33%
Total
29
100.00%
6
100.00%

#ifdef CONFIG_SMP

#include "sched-pelt.h"

static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
static unsigned long task_h_load(struct task_struct *p);

/* Give new sched_entity start runnable values to heavy its load in infant time */


void init_entity_runnable_average(struct sched_entity *se)
{
	struct sched_avg *sa = &se->avg;

	memset(sa, 0, sizeof(*sa));

	/*
         * Tasks are intialized with full load to be seen as heavy tasks until
         * they get a chance to stabilize to their real load level.
         * Group entities are intialized with zero load to reflect the fact that
         * nothing has been attached to the task group yet.
         */
	if (entity_is_task(se))
		sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight);

	se->runnable_weight = se->load.weight;

	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Yuyang Du
29
42.03%
3
42.86%
Peter Zijlstra
19
27.54%
2
28.57%
Alex Shi
13
18.84%
1
14.29%
Vincent Guittot
8
11.59%
1
14.29%
Total
69
100.00%
7
100.00%

static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
static void attach_entity_cfs_rq(struct sched_entity *se);

/*
 * With new tasks being created, their initial util_avgs are extrapolated
 * based on the cfs_rq's current util_avg:
 *
 *   util_avg = cfs_rq->util_avg / (cfs_rq->load_avg + 1) * se.load.weight
 *
 * However, in many cases, the above util_avg does not give a desired
 * value. Moreover, the sum of the util_avgs may be divergent, such
 * as when the series is a harmonic series.
 *
 * To solve this problem, we also cap the util_avg of successive tasks to
 * only 1/2 of the left utilization budget:
 *
 *   util_avg_cap = (1024 - cfs_rq->avg.util_avg) / 2^n
 *
 * where n denotes the nth task.
 *
 * For example, a simplest series from the beginning would be like:
 *
 *  task  util_avg: 512, 256, 128,  64,  32,   16,    8, ...
 * cfs_rq util_avg: 512, 768, 896, 960, 992, 1008, 1016, ...
 *
 * Finally, that extrapolated util_avg is clamped to the cap (util_avg_cap)
 * if util_avg > util_avg_cap.
 */


void post_init_entity_util_avg(struct sched_entity *se)
{
	struct cfs_rq *cfs_rq = cfs_rq_of(se);
	struct sched_avg *sa = &se->avg;
	long cap = (long)(SCHED_CAPACITY_SCALE - cfs_rq->avg.util_avg) / 2;

	if (cap > 0) {
		if (cfs_rq->avg.util_avg != 0) {
			sa->util_avg  = cfs_rq->avg.util_avg * se->load.weight;
			sa->util_avg /= (cfs_rq->avg.load_avg + 1);

			if (sa->util_avg > cap)
				sa->util_avg = cap;
		} else {
			sa->util_avg = cap;
		}
	}

	if (entity_is_task(se)) {
		struct task_struct *p = task_of(se);
		if (p->sched_class != &fair_sched_class) {
			/*
                         * For !fair tasks do:
                         *
                        update_cfs_rq_load_avg(now, cfs_rq);
                        attach_entity_load_avg(cfs_rq, se);
                        switched_from_fair(rq, p);
                         *
                         * such that the next switched_to_fair() has the
                         * expected state.
                         */
			se->avg.last_update_time = cfs_rq_clock_task(cfs_rq);
			return;
		}
	}

	attach_entity_cfs_rq(se);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Yuyang Du
119
70.41%
2
33.33%
Peter Zijlstra
42
24.85%
1
16.67%
Vincent Guittot
5
2.96%
1
16.67%
Alex Shi
2
1.18%
1
16.67%
Viresh Kumar
1
0.59%
1
16.67%
Total
169
100.00%
6
100.00%

#else /* !CONFIG_SMP */


void init_entity_runnable_average(struct sched_entity *se)
{
}
Contributors
Person
Tokens
Prop
Commits
CommitProp
Alex Shi
6
66.67%
1
50.00%
Yuyang Du
3
33.33%
1
50.00%
Total
9
100.00%
2
100.00%



void post_init_entity_util_avg(struct sched_entity *se)
{
}
Contributors
Person
Tokens
Prop
Commits
CommitProp
Yuyang Du
9
100.00%
1
100.00%
Total
9
100.00%
1
100.00%



static void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
{
}
Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
13
100.00%
1
100.00%
Total
13
100.00%
1
100.00%

#endif /* CONFIG_SMP */

/*
 * Update the current task's runtime statistics.
 */


static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;

	if (unlikely(!curr))
		return;

	delta_exec = now - curr->exec_start;
	if (unlikely((s64)delta_exec <= 0))
		return;

	curr->exec_start = now;

	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));

	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);

	curr->vruntime += calc_delta_fair(delta_exec, curr);
	update_min_vruntime(cfs_rq);

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

		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
		cgroup_account_cputime(curtask, delta_exec);
		account_group_exec_runtime(curtask, delta_exec);
	}

	account_cfs_rq_runtime(cfs_rq, delta_exec);
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Peter Zijlstra
95
55.23%
3
25.00%
Ingo Molnar
47
27.33%
3
25.00%
Arjan van de Ven
15
8.72%
1
8.33%
Paul Turner
7
4.07%
1
8.33%
Frédéric Weisbecker
3
1.74%
1
8.33%
Frank Mayhar
3
1.74%
1
8.33%
Tejun Heo
1
0.58%
1
8.33%
Josh Poimboeuf
1
0.58%
1
8.33%
Total
172
100.00%
12
100.00%



static void update_curr_fair(struct rq *rq)
{
	update_curr(cfs_rq_of(&rq->curr->se));
}

Contributors
Person
Tokens
Prop
Commits
CommitProp
Stanislaw Gruszka
24
100.00%
1
100.00%
Total
24
100.00%
1
100.00%


static inline