reduce overhead for tg->shares distribution
Subsystems (2)
PATCH v4 9/11 sched: demand based update_cfs_load()
In reply to Paul TurnerWhen the system is busy, dilation of rq->next_balance makes lb->update_shares() insufficiently frequent for threads which don't sleep (no dequeue/enqueue updates). Adjust for this by making demand based updates based on the accumulation of execution time sufficient to wrap our averaging window.
--- kernel/sched.c | 9 ++++++++- kernel/sched_fair.c | 12 ++++++++++++ 2 files changed, 20 insertions(+), 1 deletion(-)
kernel/sched.c +8 -1
@@ -353,9 +353,16 @@ struct cfs_rq {*/ unsigned long h_load; +/* +* Maintaining per-cpu shares distribution for group scheduling +* +* load_stamp is the last time we updated the load average +* load_last is the last time we updated the load average and saw load +* load_unacc_exec_time is currently unaccounted execution time +*/ u64 load_avg;u64 load_period; -u64 load_stamp, load_last; +u64 load_stamp, load_last, load_unacc_exec_time;unsigned long load_contribution;#endif
kernel/sched_fair.c +12 -0
@@ -539,6 +539,9 @@ static u64 sched_vslice(struct cfs_rq *creturn calc_delta_fair (sched_slice (cfs_rq, se), se); } +static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta); +/* * Update the current task's runtime statistics. Skip current tasks that * are not in our scheduling class.
@@ -558,6 +561,14 @@ __update_curr(struct cfs_rq *cfs_rq, str curr->vruntime += delta_exec_weighted;update_min_vruntime (cfs_rq); + +#ifdef CONFIG_FAIR_GROUP_SCHED + cfs_rq->load_unacc_exec_time += delta_exec; +if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) { +update_cfs_load (cfs_rq); +update_cfs_shares (cfs_rq,0 ); + } +#endif }static void update_curr (struct cfs_rq *cfs_rq)
@@ -713,6 +724,7 @@ static void update_cfs_load(struct cfs_r } cfs_rq->load_stamp = now; + cfs_rq->load_unacc_exec_time =0 ; cfs_rq->load_period += delta;if (load) { cfs_rq->load_last = now;
PATCH v4 6/11 sched: hierarchal order on shares update list
In reply to Paul TurnerAvoid duplicate shares update calls by ensuring children always appear before parents in rq->leaf_cfs_rq_list.
This allows us to do a single in-order traversal for update_shares().
Since we always enqueue in bottom-up order this reduces to 2 cases:
1) Our parent is already in the list, e.g.
root
\
b
/\
c d* (root->b->c already enqueued)Since d's parent is enqueued we push it to the head of the list, implicitly ahead of b.
2) Our parent does not appear in the list (or we have no parent)
In this case we enqueue to the tail of the list, if our parent is subsequently enqueued (bottom-up) it will appear to our right by the same rule.
--- kernel/sched_fair.c | 26 ++++++++++++++++---------- 1 file changed, 16 insertions(+), 10 deletions(-)
kernel/sched_fair.c +16 -10
@@ -146,8 +146,20 @@ static inline struct cfs_rq *cpu_cfs_rq(static inline void list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq) {if (!cfs_rq->on_list) { -list_add_rcu (&cfs_rq->leaf_cfs_rq_list, +/* +* 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. +*/ +if (cfs_rq->tg->parent && + cfs_rq->tg->parent->cfs_rq[cpu_of (rq_of (cfs_rq))]->on_list) { +list_add_rcu (&cfs_rq->leaf_cfs_rq_list, + &rq_of (cfs_rq)->leaf_cfs_rq_list); + }else { +list_add_tail_rcu (&cfs_rq->leaf_cfs_rq_list, &rq_of (cfs_rq)->leaf_cfs_rq_list); + } cfs_rq->on_list =1 ; }
@@ -2010,7 +2022,7 @@ out:/* * update tg->load_weight by folding this cpu's load_avg */ -static int tg_shares_up (struct task_group *tg,int cpu) +static int update_shares_cpu (struct task_group *tg,int cpu) {struct cfs_rq *cfs_rq;unsigned long flags;
@@ -2050,14 +2062,8 @@ static void update_shares(int cpu)struct rq *rq =cpu_rq (cpu);rcu_read_lock (); -for_each_leaf_cfs_rq (rq, cfs_rq) { -struct task_group *tg = cfs_rq->tg; - -do { -tg_shares_up (tg, cpu); - tg = tg->parent; - }while (tg); - } +for_each_leaf_cfs_rq (rq, cfs_rq) +update_shares_cpu (cfs_rq->tg, cpu);rcu_read_unlock (); }
PATCH v4 7/11 sched: add sysctl_sched_shares_window
In reply to Paul TurnerIntroduce a new sysctl for the shares window and disambiguate it from sched_time_avg.
A 10ms window appears to be a good compromise between accuracy and performance.
--- include/linux/sched.h | 1 + kernel/sched_fair.c | 9 ++++++++- kernel/sysctl.c | 7 +++++++ 3 files changed, 16 insertions(+), 1 deletion(-)
kernel/sched_fair.c +8 -1
@@ -89,6 +89,13 @@ unsigned int normalized_sysctl_sched_wak const_debug unsigned int sysctl_sched_migration_cost = 500000UL; +/* +* The exponential sliding window over which load is averaged for shares +* distribution. +* (default: 10msec) +*/ +unsigned int __read_mostly sysctl_sched_shares_window =10000000UL ; +static const struct sched_class fair_sched_class;/**************************************************************
@@ -688,7 +695,7 @@ account_entity_dequeue(struct cfs_rq *cf#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED static void update_cfs_load (struct cfs_rq *cfs_rq) { -u64 period =sched_avg_period (); +u64 period = sysctl_sched_shares_window;u64 now, delta;unsigned long load = cfs_rq->load.weight;
include/linux/sched.h +1 -0
@@ -1904,6 +1904,7 @@ extern unsigned int sysctl_sched_migratiextern unsigned int sysctl_sched_nr_migrate;extern unsigned int sysctl_sched_time_avg;extern unsigned int sysctl_timer_migration; +extern unsigned int sysctl_sched_shares_window; int sched_proc_update_handler(struct ctl_table *table, int write, void __user *buffer, size_t *length,
kernel/sysctl.c +7 -0
@@ -333,6 +333,13 @@ static struct ctl_table kern_table[] = { .proc_handler = proc_dointvec, }, { + .procname = "sched_shares_window", + .data = &sysctl_sched_shares_window, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = proc_dointvec, + }, + { .procname = "timer_migration", .data = &sysctl_timer_migration, .maxlen = sizeof(unsigned int),
PATCH v4 3/11 sched: make tg_shares_up() walk on-demand
In reply to Paul TurnerFrom: Peter Zijlstra <[email protected]>
Make tg_shares_up() use the active cgroup list, this means we cannot do a strict bottom-up walk of the hierarchy, but assuming its a very wide tree with a small number of active groups it should be a win.
--- kernel/sched.c | 67 ---------------------------------------------------- kernel/sched_fair.c | 58 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+), 67 deletions(-)
kernel/sched.c +0 -67
@@ -279,13 +279,6 @@ static DEFINE_SPINLOCK(task_group_lock);#ifdef CONFIG_FAIR_GROUP_SCHED -#ifdef CONFIG_SMP -static int root_task_group_empty (void ) -{ -return list_empty (&root_task_group.children); -} -#endif -# define INIT_TASK_GROUP_LOAD NICE_0_LOAD/*
@@ -1536,48 +1529,6 @@ static unsigned long cpu_avg_load_per_ta#ifdef CONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq,int lb); -static void update_cfs_shares (struct cfs_rq *cfs_rq); - -/* -* update tg->load_weight by folding this cpu's load_avg -*/ -static int tg_shares_up (struct task_group *tg,void *data) -{ -long load_avg; -struct cfs_rq *cfs_rq; -unsigned long flags; -int cpu = (long )data; -struct rq *rq; - -if (!tg->se[cpu]) -return 0 ; - - rq =cpu_rq (cpu); - cfs_rq = tg->cfs_rq[cpu]; - -raw_spin_lock_irqsave (&rq->lock, flags); - -update_rq_clock (rq); -update_cfs_load (cfs_rq,1 ); - - load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); - load_avg -= cfs_rq->load_contribution; - -atomic_add (load_avg, &tg->load_weight); - cfs_rq->load_contribution += load_avg; - -/* -* We need to update shares after updating tg->load_weight in -* order to adjust the weight of groups with long running tasks. -*/ -update_cfs_shares (cfs_rq); - -raw_spin_unlock_irqrestore (&rq->lock, flags); - -return 0 ; -} -/* * Compute the cpu's hierarchical load factor for each task group. * This needs to be done in a top-down fashion because the load of a child
@@ -1601,29 +1552,11 @@ static int tg_load_down(struct task_grou return 0; } -static void update_shares (long cpu) -{ -if (root_task_group_empty ()) -return ; - -/* -* XXX: replace with an on-demand list -*/ - -walk_tg_tree (tg_nop, tg_shares_up, (void *)cpu); -} -static void update_h_load (long cpu) {walk_tg_tree (tg_load_down, tg_nop, (void *)cpu); } -#else - -static inline void update_shares (int cpu) -{ -} -#endif #ifdef CONFIG_PREEMPT
kernel/sched_fair.c +58 -0
70 lines not on this page · raw message
PATCH v4 8/11 sched: update shares on idle_balance
In reply to Paul TurnerSince shares updates are no longer expensive and effectively local, update them at idle_balance(). This allows us to more quickly redistribute shares to another cpu when our load becomes idle.
--- kernel/sched_fair.c | 1 + 1 file changed, 1 insertion(+)
kernel/sched_fair.c +1 -0
@@ -3365,6 +3365,7 @@ static void idle_balance(int this_cpu, s*/ raw_spin_unlock (&this_rq->lock); +update_shares (this_cpu);for_each_domain (this_cpu, sd) {unsigned long interval;int balance =1 ;
PATCH v4 10/11 sched: allow update_cfs_load to update global load
In reply to Paul TurnerRefactor the global load updates from update_shares_cpu() so that update_cfs_load() can update global load when it is more than ~10% out of sync.
The new global_load parameter allows us to force an update, regardless of the error factor so that we can synchronize w/ update_shares().
--- kernel/sched_fair.c | 44 +++++++++++++++++++++++++++++--------------- 1 file changed, 29 insertions(+), 15 deletions(-)
kernel/sched_fair.c +29 -15
@@ -539,7 +539,7 @@ static u64 sched_vslice(struct cfs_rq *creturn calc_delta_fair (sched_slice (cfs_rq, se), se); } -static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update);static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta);/*
@@ -565,7 +565,7 @@ __update_curr(struct cfs_rq *cfs_rq, str#ifdef CONFIG_FAIR_GROUP_SCHED cfs_rq->load_unacc_exec_time += delta_exec;if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) { -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }#endif
@@ -704,7 +704,22 @@ account_entity_dequeue(struct cfs_rq *cf }#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq) +static void update_cfs_rq_load_contribution (struct cfs_rq *cfs_rq, +int global_update) +{ +struct task_group *tg = cfs_rq->tg; +long load_avg; + + load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); + load_avg -= cfs_rq->load_contribution; + +if (global_update ||abs (load_avg) > cfs_rq->load_contribution /8 ) { +atomic_add (load_avg, &tg->load_weight); + cfs_rq->load_contribution += load_avg; + } +} + +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update) {u64 period = sysctl_sched_shares_window;u64 now, delta;
@@ -731,6 +746,11 @@ static void update_cfs_load(struct cfs_r cfs_rq->load_avg += delta * load; } +/* consider updating load contribution on each fold or truncate */ +if (global_update || cfs_rq->load_period > period + || !cfs_rq->load_period) +update_cfs_rq_load_contribution (cfs_rq, global_update); +while (cfs_rq->load_period > period) {/* * Inline assembly required to prevent the compiler
@@ -790,7 +810,7 @@ static void update_cfs_shares(struct cfs reweight_entity(cfs_rq_of(se), se, shares); }#else /* CONFIG_FAIR_GROUP_SCHED */ -static inline void update_cfs_load (struct cfs_rq *cfs_rq) +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update) { }
@@ -920,7 +940,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se);
@@ -981,7 +1001,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, stif (se != cfs_rq->curr)__dequeue_entity (cfs_rq, se); se->on_rq =0 ; -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq);update_cfs_shares (cfs_rq,0 );
@@ -1216,7 +1236,7 @@ enqueue_task_fair(struct rq *rq, structfor_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }
@@ -1246,7 +1266,7 @@ static void dequeue_task_fair(struct rqfor_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }
@@ -2046,7 +2066,6 @@ static int update_shares_cpu(struct taskstruct cfs_rq *cfs_rq;unsigned long flags;struct rq *rq; -long load_avg;if (!tg->se[cpu])return 0 ;
@@ -2057,12 +2076,7 @@ static int update_shares_cpu(struct taskraw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq); - - load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); - load_avg -= cfs_rq->load_contribution; -atomic_add (load_avg, &tg->load_weight); - cfs_rq->load_contribution += load_avg; +update_cfs_load (cfs_rq,1 );/* * We need to update shares after updating tg->load_weight in
PATCH v4 11/11 sched: update tg->shares after cpu.shares write
In reply to Paul TurnerFormerly sched_group_set_shares would force a rebalance by overflowing domain share sums. Now that per-cpu averages are maintained we can set the true value by issuing an update_cfs_shares() following a tg->shares update.
Also initialize tg se->load to 0 for consistency since we'll now set correct weights on enqueue.
--- kernel/sched.c | 42 +++++++++++------------------------------- 1 file changed, 11 insertions(+), 31 deletions(-)
kernel/sched.c +11 -31
@@ -7747,7 +7747,7 @@ static void init_tg_cfs_entry(struct tas se->cfs_rq = parent->my_q; se->my_q = cfs_rq; -update_load_set (&se->load, tg->shares); +update_load_set (&se->load,0 ); se->parent = parent; }#endif
@@ -8375,37 +8375,12 @@ void sched_move_task(struct task_struct#endif /* CONFIG_CGROUP_SCHED */ #ifdef CONFIG_FAIR_GROUP_SCHED -static void __set_se_shares (struct sched_entity *se,unsigned long shares) -{ -struct cfs_rq *cfs_rq = se->cfs_rq; -int on_rq; - - on_rq = se->on_rq; -if (on_rq) -dequeue_entity (cfs_rq, se,0 ); - -update_load_set (&se->load, shares); - -if (on_rq) -enqueue_entity (cfs_rq, se,0 ); -} - -static void set_se_shares (struct sched_entity *se,unsigned long shares) -{ -struct cfs_rq *cfs_rq = se->cfs_rq; -struct rq *rq = cfs_rq->rq; -unsigned long flags; - -raw_spin_lock_irqsave (&rq->lock, flags); -__set_se_shares (se, shares); -raw_spin_unlock_irqrestore (&rq->lock, flags); -} -static DEFINE_MUTEX (shares_mutex);int sched_group_set_shares (struct task_group *tg,unsigned long shares) {int i; +unsigned long flags;/* * We can't change the weight of the root cgroup.
@@ -8424,10 +8399,15 @@ int sched_group_set_shares(struct task_g tg->shares = shares;for_each_possible_cpu (i) { -/* -* force a rebalance -*/ -set_se_shares (tg->se[i], shares); +struct rq *rq =cpu_rq (i); +struct sched_entity *se; + + se = tg->se[i]; +/* Propagate contribution to hierarchy */ +raw_spin_lock_irqsave (&rq->lock, flags); +for_each_sched_entity (se) +update_cfs_shares (group_cfs_rq (se),0 ); +raw_spin_unlock_irqrestore (&rq->lock, flags); } done:
PATCH v4 4/11 sched: fix load corruption from update_cfs_shares
In reply to Paul Turneras part of enqueue_entity both a new entity weight and its contribution to the queuing cfs_rq / rq are updated. Since update_cfs_shares will only update the queueing weights when the entity is on_rq (which in this case it is not yet), there's a dependency loop here:
update_cfs_shares needs account_entity_enqueue to update cfs_rq->load.weight account_entity_enqueue needs the updated weight for the queuing cfs_rq load[*]
Fix this and avoid spurious dequeue/enqueues by issuing update_cfs_shares as if we had accounted the enqueue already.
This was also resulting in rq->load corruption previously.
[*]: this dependency also exists when using the group cfs_rq w/ update_cfs_shares as the weight of the enqueued entity changes without the load being updated.
--- kernel/sched_fair.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-)
kernel/sched_fair.c +8 -8
@@ -718,7 +718,7 @@ static void reweight_entity(struct cfs_raccount_entity_enqueue (cfs_rq, se); } -static void update_cfs_shares (struct cfs_rq *cfs_rq) +static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta) {struct task_group *tg;struct sched_entity *se;
@@ -732,7 +732,7 @@ static void update_cfs_shares(struct cfsif (!se)return ; - load = cfs_rq->load.weight; + load = cfs_rq->load.weight + weight_delta; load_weight =atomic_read (&tg->load_weight); load_weight -= cfs_rq->load_contribution;
@@ -754,7 +754,7 @@ static inline void update_cfs_load(struc { } -static inline void update_cfs_shares (struct cfs_rq *cfs_rq) +static inline void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta) { }#endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -881,8 +881,8 @@ enqueue_entity(struct cfs_rq *cfs_rq, st*/ update_curr (cfs_rq);update_cfs_load (cfs_rq,0 ); +update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se); -update_cfs_shares (cfs_rq);if (flags &ENQUEUE_WAKEUP ) {place_entity (cfs_rq, se,0 );
@@ -944,7 +944,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, stupdate_cfs_load (cfs_rq,0 );account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 );/* * Normalize the entity after updating the min_vruntime because the
@@ -1177,7 +1177,7 @@ enqueue_task_fair(struct rq *rq, structstruct cfs_rq *cfs_rq =cfs_rq_of (se);update_cfs_load (cfs_rq,0 ); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 ); }hrtick_update (rq);
@@ -1207,7 +1207,7 @@ static void dequeue_task_fair(struct rqstruct cfs_rq *cfs_rq =cfs_rq_of (se);update_cfs_load (cfs_rq,0 ); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 ); }hrtick_update (rq);
@@ -2028,7 +2028,7 @@ static int tg_shares_up(struct task_grou* We need to update shares after updating tg->load_weight in * order to adjust the weight of groups with long running tasks. */ -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 );raw_spin_unlock_irqrestore (&rq->lock, flags);
PATCH v4 1/11 sched: rewrite tg_shares_up
In reply to Paul TurnerFrom: Peter Zijlstra <[email protected]>
By tracking a per-cpu load-avg for each cfs_rq and folding it into a global task_group load on each tick we can rework tg_shares_up to be strictly per-cpu.
This should improve cpu-cgroup performance for smp systems significantly.
[ Paul: changed to use queueing cfs_rq + bug fixes ]
--- include/linux/sched.h | 2 kernel/sched.c | 173 ++++++++++++------------------------------------ kernel/sched_debug.c | 15 +++- kernel/sched_fair.c | 164 +++++++++++++++++++++++++++++---------------- kernel/sched_features.h | 2 kernel/sysctl.c | 19 ----- 6 files changed, 162 insertions(+), 213 deletions(-)
include/linux/sched.h +0 -2
@@ -1889,8 +1889,6 @@ static inline void wake_up_idle_cpu(intextern unsigned int sysctl_sched_latency;extern unsigned int sysctl_sched_min_granularity;extern unsigned int sysctl_sched_wakeup_granularity; -extern unsigned int sysctl_sched_shares_ratelimit; -extern unsigned int sysctl_sched_shares_thresh;extern unsigned int sysctl_sched_child_runs_first;enum sched_tunable_scaling {
kernel/sched.c +44 -129
278 lines not on this page · raw message
kernel/sched_debug.c +11 -4
@@ -202,15 +202,22 @@ void print_cfs_rq(struct seq_file *m, in spread0 = min_vruntime - rq0_min_vruntime;SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"spread0" ,SPLIT_NS (spread0)); -SEQ_printf (m," .%-30s: %ld\n" ,"nr_running" , cfs_rq->nr_running); -SEQ_printf (m," .%-30s: %ld\n" ,"load" , cfs_rq->load.weight); -SEQ_printf (m," .%-30s: %d\n" ,"nr_spread_over" , cfs_rq->nr_spread_over); +SEQ_printf (m," .%-30s: %ld\n" ,"nr_running" , cfs_rq->nr_running); +SEQ_printf (m," .%-30s: %ld\n" ,"load" , cfs_rq->load.weight);#ifdef CONFIG_FAIR_GROUP_SCHED #ifdef CONFIG_SMP -SEQ_printf (m," .%-30s: %lu\n" ,"shares" , cfs_rq->shares); +SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"load_avg" , +SPLIT_NS (cfs_rq->load_avg)); +SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"load_period" , +SPLIT_NS (cfs_rq->load_period)); +SEQ_printf (m," .%-30s: %ld\n" ,"load_contrib" , + cfs_rq->load_contribution); +SEQ_printf (m," .%-30s: %d\n" ,"load_tg" , +atomic_read (&tg->load_weight));#endif +print_cfs_group_stats (m, cpu, cfs_rq->tg);#endif }
kernel/sched_fair.c +107 -57
264 lines not on this page · raw message
kernel/sched_features.h +0 -2
@@ -52,8 +52,6 @@ SCHED_FEAT(ARCH_POWER, 0) SCHED_FEAT(HRTICK, 0) SCHED_FEAT(DOUBLE_TICK, 0)SCHED_FEAT (LB_BIAS ,1 ) -SCHED_FEAT(LB_SHARES_UPDATE, 1) -SCHED_FEAT (ASYM_EFF_LOAD ,1 )/* * Spin-wait on mutex acquisition when the mutex owner is running on
kernel/sysctl.c +0 -19
@@ -259,8 +259,6 @@ static int min_wakeup_granularity_ns;static int max_wakeup_granularity_ns =NSEC_PER_SEC ;/* 1 second */ static int min_sched_tunable_scaling =SCHED_TUNABLESCALING_NONE ;static int max_sched_tunable_scaling =SCHED_TUNABLESCALING_END -1 ; -static int min_sched_shares_ratelimit =100000 ;/* 100 usec */ -static int max_sched_shares_ratelimit =NSEC_PER_SEC ;/* 1 second */ #endif #ifdef CONFIG_COMPACTION
@@ -305,15 +303,6 @@ static struct ctl_table kern_table[] = { .extra2 = &max_wakeup_granularity_ns, }, { - .procname = "sched_shares_ratelimit", - .data = &sysctl_sched_shares_ratelimit, - .maxlen = sizeof(unsigned int), - .mode = 0644, - .proc_handler = sched_proc_update_handler, - .extra1 = &min_sched_shares_ratelimit, - .extra2 = &max_sched_shares_ratelimit, - }, - { .procname = "sched_tunable_scaling", .data = &sysctl_sched_tunable_scaling, .maxlen = sizeof(enum sched_tunable_scaling),
@@ -323,14 +312,6 @@ static struct ctl_table kern_table[] = { .extra2 = &max_sched_tunable_scaling, }, { - .procname = "sched_shares_thresh", - .data = &sysctl_sched_shares_thresh, - .maxlen = sizeof(unsigned int), - .mode = 0644, - .proc_handler = proc_dointvec_minmax, - .extra1 = &zero, - }, - { .procname = "sched_migration_cost", .data = &sysctl_sched_migration_cost, .maxlen = sizeof(unsigned int),
v4 cover reduce overhead for tg->shares distribution
This is v4 of the tg_shares_up re-write previously posted at:
http://lkml.org/lkml/2010/10/16/17
Corrected versus the previous version is the quilt patch-strip level.
The key idea behind this patchset is an idea of Peter Zijlstra'a to compute global loads as a function of local averages, avoiding the cpu-cpu interactions which previously plagued tg_shares_up.
Beyond bug fixes not much material has changed since v1 as results seem favourable/stable.
Changes:
v4
all patches
- fix "-p0" stripping
v3 (http://lkml.org/lkml/2010/11/11/526)
sched-rework-tg_shares_up.patch
- remove lint: {max,min}_sched_shares_ratelimit from sysctl.c
sched-tg-ondemand.patch
- (bug fix) fix synchronization on leaf_cfs_rq_list removal during task_group reclaim.
- fix !CONFIG_FAIR_GROUP_SCHED build
- fix comment on what task_group_lock protects
sched-tg-global_update_load.patch
- add missing arguments to update_cfs_load() in !CONFIG_FAIR_GROUP_SCHED case
v2 (http://lkml.org/lkml/2010/11/10/618)
sched-rework-tg_shares_up.patch
- (bug fix) use owning tg->shares value in effective_load
- remove redundant cfs_rq_of() in {enqueue,dequeue}_entity
sched-tg-add-shares_window_sysctl.patch
- update comment on sysctl interpretation
sched-tg-fix-update_cfs_load.patch
- update comment to reflect periods instead of foldings (more intuitive)
Some motivation again:
24 thread Intel box, 150 active cgroups, multiple threads/group, system load at ~90% (sample size=10s):
tip:
2.64% [k] tg_shares_up <!>
0.15% [k] __set_se_sharespatched:
0.02% [k] update_cfs_load
0.01% [k] update_cpu_load
0.00% [k] update_cfs_sharesFairness coverage for the above at: http://rs5.risingnet.net/~pjt/patches/shares_data_v1.txt
Thanks,
- Paul
PATCH v4 2/11 sched: on-demand (active) cfs_rq list
From: Peter Zijlstra <[email protected]>
Make certain load-balance actions scale per number of active cgroups instead of the number of existing cgroups.
This makes wakeup/sleep paths more expensive, but is a win for systems where the vast majority of existing cgroups are idle.
--- kernel/sched.c | 105 +++++++++++++--------------------------------------- kernel/sched_fair.c | 46 +++++++++++++++++++--- kernel/sched_rt.c | 24 +++++++++++ 3 files changed, 92 insertions(+), 83 deletions(-)
kernel/sched.c +28 -77
@@ -274,9 +274,7 @@ struct task_group {#define root_task_group init_task_group -/* task_group_lock serializes add/remove of task groups and also changes to -* a task group's cpu shares. -*/ +/* task_group_lock serializes the addition/removal of task groups */ static DEFINE_SPINLOCK (task_group_lock);#ifdef CONFIG_FAIR_GROUP_SCHED
@@ -344,6 +342,7 @@ struct cfs_rq {* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This * list is used during load balance. */ +int on_list;struct list_head leaf_cfs_rq_list;struct task_group *tg;/* group that "owns" this runqueue */
@@ -1537,7 +1536,7 @@ static unsigned long cpu_avg_load_per_ta#ifdef CONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_load (struct cfs_rq *cfs_rq,int lb);static void update_cfs_shares (struct cfs_rq *cfs_rq);/*
@@ -1560,7 +1559,7 @@ static int tg_shares_up(struct task_grouraw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,1 ); load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); load_avg -= cfs_rq->load_contribution;
@@ -7789,15 +7788,13 @@ static void init_rt_rq(struct rt_rq *rt_#ifdef CONFIG_FAIR_GROUP_SCHED static void init_tg_cfs_entry (struct task_group *tg,struct cfs_rq *cfs_rq, -struct sched_entity *se,int cpu,int add, +struct sched_entity *se,int cpu,struct sched_entity *parent) {struct rq *rq =cpu_rq (cpu); tg->cfs_rq[cpu] = cfs_rq;init_cfs_rq (cfs_rq, rq); cfs_rq->tg = tg; -if (add) -list_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se;/* se could be NULL for init_task_group */
@@ -7817,7 +7814,7 @@ static void init_tg_cfs_entry(struct tas#ifdef CONFIG_RT_GROUP_SCHED static void init_tg_rt_entry (struct task_group *tg,struct rt_rq *rt_rq, -struct sched_rt_entity *rt_se,int cpu,int add, +struct sched_rt_entity *rt_se,int cpu,struct sched_rt_entity *parent) {struct rq *rq =cpu_rq (cpu);
@@ -7826,8 +7823,6 @@ static void init_tg_rt_entry(struct taskinit_rt_rq (rt_rq, rq); rt_rq->tg = tg; rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime; -if (add) -list_add (&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list); tg->rt_se[cpu] = rt_se;if (!rt_se)
@@ -7936,7 +7931,7 @@ void __init sched_init(void)* We achieve this by letting init_task_group's tasks sit * directly in rq->cfs (i.e init_task_group->se[] = NULL). */ -init_tg_cfs_entry (&init_task_group, &rq->cfs,NULL , i,1 ,NULL ); +init_tg_cfs_entry (&init_task_group, &rq->cfs,NULL , i,NULL );#endif #endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -7944,7 +7939,7 @@ void __init sched_init(void)#ifdef CONFIG_RT_GROUP_SCHED INIT_LIST_HEAD (&rq->leaf_rt_rq_list);#ifdef CONFIG_CGROUP_SCHED -init_tg_rt_entry (&init_task_group, &rq->rt,NULL , i,1 ,NULL ); +init_tg_rt_entry (&init_task_group, &rq->rt,NULL , i,NULL );#endif #endif
@@ -8220,7 +8215,7 @@ int alloc_fair_sched_group(struct task_gif (!se) goto err_free_rq; -init_tg_cfs_entry (tg, cfs_rq, se, i,0 , parent->se[i]); +init_tg_cfs_entry (tg, cfs_rq, se, i, parent->se[i]); }return 1 ;
@@ -8231,15 +8226,22 @@ err: return 0; } -static inline void register_fair_sched_group (struct task_group *tg,int cpu) -{ -list_add_rcu (&tg->cfs_rq[cpu]->leaf_cfs_rq_list, - &cpu_rq (cpu)->leaf_cfs_rq_list); -} -static inline void unregister_fair_sched_group (struct task_group *tg,int cpu) { -list_del_rcu (&tg->cfs_rq[cpu]->leaf_cfs_rq_list); +struct rq *rq =cpu_rq (cpu); +unsigned long flags; +int i; + +/* +* Only empty task groups can be destroyed; so we can speculatively +* check on_list without danger of it being re-added. +*/ +if (!tg->cfs_rq[cpu]->on_list) +return ; + +raw_spin_lock_irqsave (&rq->lock, flags); +list_del_leaf_cfs_rq (tg->cfs_rq[i]); +raw_spin_unlock_irqrestore (&rq->lock, flags); }#else /* !CONFG_FAIR_GROUP_SCHED */ static inline void free_fair_sched_group (struct task_group *tg)
@@ -8252,10 +8254,6 @@ int alloc_fair_sched_group(struct task_greturn 1 ; } -static inline void register_fair_sched_group (struct task_group *tg,int cpu) -{ -} -static inline void unregister_fair_sched_group (struct task_group *tg,int cpu) { }
@@ -8310,7 +8308,7 @@ int alloc_rt_sched_group(struct task_groif (!rt_se) goto err_free_rq; -init_tg_rt_entry (tg, rt_rq, rt_se, i,0 , parent->rt_se[i]); +init_tg_rt_entry (tg, rt_rq, rt_se, i, parent->rt_se[i]); }return 1 ;
@@ -8320,17 +8318,6 @@ err_free_rq: err: return 0; } - -static inline void register_rt_sched_group (struct task_group *tg,int cpu) -{ -list_add_rcu (&tg->rt_rq[cpu]->leaf_rt_rq_list, - &cpu_rq (cpu)->leaf_rt_rq_list); -} - -static inline void unregister_rt_sched_group (struct task_group *tg,int cpu) -{ -list_del_rcu (&tg->rt_rq[cpu]->leaf_rt_rq_list); -}#else /* !CONFIG_RT_GROUP_SCHED */ static inline void free_rt_sched_group (struct task_group *tg) {
@@ -8341,14 +8328,6 @@ int alloc_rt_sched_group(struct task_gro {return 1 ; } - -static inline void register_rt_sched_group (struct task_group *tg,int cpu) -{ -} - -static inline void unregister_rt_sched_group (struct task_group *tg,int cpu) -{ -}#endif /* CONFIG_RT_GROUP_SCHED */ #ifdef CONFIG_CGROUP_SCHED
@@ -8364,7 +8343,6 @@ struct task_group *sched_create_group(st {struct task_group *tg;unsigned long flags; -int i; tg =kzalloc (sizeof (*tg),GFP_KERNEL );if (!tg)
@@ -8377,10 +8355,6 @@ struct task_group *sched_create_group(st goto err;spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) { -register_fair_sched_group (tg, i); -register_rt_sched_group (tg, i); - }list_add_rcu (&tg->list, &task_groups);WARN_ON (!parent);/* root should already exist */
@@ -8410,11 +8384,11 @@ void sched_destroy_group(struct task_grounsigned long flags;int i; -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) { +/* end participation in shares distribution */ +for_each_possible_cpu (i)unregister_fair_sched_group (tg, i); -unregister_rt_sched_group (tg, i); - } + +spin_lock_irqsave (&task_group_lock, flags);list_del_rcu (&tg->list);list_del_rcu (&tg->siblings);spin_unlock_irqrestore (&task_group_lock, flags);
@@ -8492,7 +8466,6 @@ static DEFINE_MUTEX(shares_mutex);int sched_group_set_shares (struct task_group *tg,unsigned long shares) {int i; -unsigned long flags;/* * We can't change the weight of the root cgroup.
@@ -8509,19 +8482,6 @@ int sched_group_set_shares(struct task_gif (tg->shares == shares) goto done; -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) -unregister_fair_sched_group (tg, i); -list_del_rcu (&tg->siblings); -spin_unlock_irqrestore (&task_group_lock, flags); - -/* wait for any ongoing reference to this group to finish */ -synchronize_sched (); - -/* -* Now we are free to modify the group's share on each cpu -* w/o tripping rebalance_share or load_balance_fair. -*/ tg->shares = shares;for_each_possible_cpu (i) {/*
@@ -8530,15 +8490,6 @@ int sched_group_set_shares(struct task_gset_se_shares (tg->se[i], shares); } -/* -* Enable load balance activity on this group, by inserting it back on -* each cpu's rq->leaf_cfs_rq_list. -*/ -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) -register_fair_sched_group (tg, i); -list_add_rcu (&tg->siblings, &tg->parent->children); -spin_unlock_irqrestore (&task_group_lock, flags); done:mutex_unlock (&shares_mutex);return 0 ;
kernel/sched_fair.c +40 -6
106 lines not on this page · raw message
kernel/sched_rt.c +24 -0
@@ -183,6 +183,17 @@ static inline u64 sched_rt_period(structreturn ktime_to_ns (rt_rq->tg->rt_bandwidth.rt_period); } +static inline void list_add_leaf_rt_rq (struct rt_rq *rt_rq) +{ +list_add_rcu (&rt_rq->leaf_rt_rq_list, + &rq_of_rt_rq (rt_rq)->leaf_rt_rq_list); +} + +static inline void list_del_leaf_rt_rq (struct rt_rq *rt_rq) +{ +list_del_rcu (&rt_rq->leaf_rt_rq_list); +} +#define for_each_leaf_rt_rq (rt_rq, rq) \ list_for_each_entry_rcu(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
@@ -276,6 +287,14 @@ static inline u64 sched_rt_period(structreturn ktime_to_ns (def_rt_bandwidth.rt_period); } +static inline void list_add_leaf_rt_rq (struct rt_rq *rt_rq) +{ +} + +static inline void list_del_leaf_rt_rq (struct rt_rq *rt_rq) +{ +} +#define for_each_leaf_rt_rq (rt_rq, rq) \ for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
@@ -825,6 +844,9 @@ static void __enqueue_rt_entity(struct sif (group_rq && (rt_rq_throttled (group_rq) || !group_rq->rt_nr_running))return ; +if (!rt_rq->rt_nr_running) +list_add_leaf_rt_rq (rt_rq); +if (head)list_add (&rt_se->run_list, queue);else
@@ -844,6 +866,8 @@ static void __dequeue_rt_entity(struct s__clear_bit (rt_se_prio (rt_se), array->bitmap);dec_rt_tasks (rt_se, rt_rq); +if (!rt_rq->rt_nr_running) +list_del_leaf_rt_rq (rt_rq); }/*
PATCH v4 5/11 sched: fix update_cfs_load synchronization
In reply to Paul TurnerUsing cfs_rq->nr_running is not sufficient to synchronize update_cfs_load with the put path since nr_running accounting occurs at deactivation.
It's also not safe to make the removal decision based on load_avg as this fails with both high periods and low shares. Resolve this by clipping history after 4 periods without activity.
Note: the above will always occur from update_shares() since in the last-task-sleep-case that task will still be cfs_rq->curr when update_cfs_load is called.
--- kernel/sched.c | 2 +- kernel/sched_fair.c | 33 +++++++++++++++++++++------------ 2 files changed, 22 insertions(+), 13 deletions(-)
kernel/sched_fair.c +21 -12
@@ -674,10 +674,11 @@ account_entity_dequeue(struct cfs_rq *cf }#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq,int lb) +static void update_cfs_load (struct cfs_rq *cfs_rq) {u64 period =sched_avg_period ();u64 now, delta; +unsigned long load = cfs_rq->load.weight;if (!cfs_rq)return ;
@@ -685,9 +686,19 @@ static void update_cfs_load(struct cfs_r now =rq_of (cfs_rq)->clock; delta = now - cfs_rq->load_stamp; +/* truncate load history at 4 idle periods */ +if (cfs_rq->load_stamp > cfs_rq->load_last && + now - cfs_rq->load_last >4 * period) { + cfs_rq->load_period =0 ; + cfs_rq->load_avg =0 ; + } + cfs_rq->load_stamp = now; cfs_rq->load_period += delta; - cfs_rq->load_avg += delta * cfs_rq->load.weight; +if (load) { + cfs_rq->load_last = now; + cfs_rq->load_avg += delta * load; + }while (cfs_rq->load_period > period) {/*
@@ -700,10 +711,8 @@ static void update_cfs_load(struct cfs_r cfs_rq->load_avg /=2 ; } -if (lb && !cfs_rq->nr_running) { -if (cfs_rq->load_avg < (period /8 )) -list_del_leaf_cfs_rq (cfs_rq); - } +if (!cfs_rq->curr && !cfs_rq->nr_running && !cfs_rq->load_avg) +list_del_leaf_cfs_rq (cfs_rq); } static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
@@ -750,7 +759,7 @@ static void update_cfs_shares(struct cfs reweight_entity(cfs_rq_of(se), se, shares); }#else /* CONFIG_FAIR_GROUP_SCHED */ -static inline void update_cfs_load (struct cfs_rq *cfs_rq,int lb) +static inline void update_cfs_load (struct cfs_rq *cfs_rq) { }
@@ -880,7 +889,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se);
@@ -941,7 +950,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, stif (se != cfs_rq->curr)__dequeue_entity (cfs_rq, se); se->on_rq =0 ; -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq);update_cfs_shares (cfs_rq,0 );
@@ -1176,7 +1185,7 @@ enqueue_task_fair(struct rq *rq, structfor_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq,0 ); }
@@ -1206,7 +1215,7 @@ static void dequeue_task_fair(struct rqfor_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq,0 ); }
@@ -2017,7 +2026,7 @@ static int tg_shares_up(struct task_grouraw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq,1 ); +update_cfs_load (cfs_rq); load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); load_avg -= cfs_rq->load_contribution;
kernel/sched.c +1 -1
@@ -355,7 +355,7 @@ struct cfs_rq {u64 load_avg;u64 load_period; -u64 load_stamp; +u64 load_stamp, load_last;unsigned long load_contribution;#endif
Peter Zijlstra
AppliedQuoted 4 lines · Paul Turner
This is v4 of the
tg_shares_upre-write previously posted at:
http://lkml.org/lkml/2010/10/16/17
Quoted 8 lines
Corrected versus the previous version is the quilt patch-strip level.
The key idea behind this patchset is an idea of Peter Zijlstra'a to compute global loads as a function of local averages, avoiding the cpu-cpu interactions which previously plagued
tg_shares_up.Beyond bug fixes not much material has changed since v1 as results seem favourable/stable.
Thanks, applied!
[tip:sched/core] sched: Rewrite tg_shares_up)
In reply to Paul TurnerCommit-ID: 2069dd75c7d0f49355939e5586daf5a9ab216db7 Gitweb: http://git.kernel.org/tip/2069dd75c7d0f49355939e5586daf5a9ab216db7 Author: Peter Zijlstra <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:00 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:46 +0100
sched: Rewrite tg_shares_up)
By tracking a per-cpu load-avg for each cfs_rq and folding it into a global task_group load on each tick we can rework tg_shares_up to be strictly per-cpu.
This should improve cpu-cgroup performance for smp systems significantly.
[ Paul: changed to use queueing cfs_rq + bug fixes ]
LKML-Reference: <[email protected]>
--- include/linux/sched.h | 2 - kernel/sched.c | 173 ++++++++++++----------------------------------- kernel/sched_debug.c | 15 +++- kernel/sched_fair.c | 164 +++++++++++++++++++++++++++++--------------- kernel/sched_features.h | 2 - kernel/sysctl.c | 19 ----- 6 files changed, 162 insertions(+), 213 deletions(-)
include/linux/sched.h +0 -2
@@ -1885,8 +1885,6 @@ static inline void wake_up_idle_cpu(int cpu) { }extern unsigned int sysctl_sched_latency;extern unsigned int sysctl_sched_min_granularity;extern unsigned int sysctl_sched_wakeup_granularity; -extern unsigned int sysctl_sched_shares_ratelimit; -extern unsigned int sysctl_sched_shares_thresh;extern unsigned int sysctl_sched_child_runs_first;enum sched_tunable_scaling {
kernel/sched.c +44 -129
278 lines not on this page · raw message
kernel/sched_debug.c +11 -4
@@ -202,15 +202,22 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) spread0 = min_vruntime - rq0_min_vruntime;SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"spread0" ,SPLIT_NS (spread0)); -SEQ_printf (m," .%-30s: %ld\n" ,"nr_running" , cfs_rq->nr_running); -SEQ_printf (m," .%-30s: %ld\n" ,"load" , cfs_rq->load.weight); -SEQ_printf (m," .%-30s: %d\n" ,"nr_spread_over" , cfs_rq->nr_spread_over); +SEQ_printf (m," .%-30s: %ld\n" ,"nr_running" , cfs_rq->nr_running); +SEQ_printf (m," .%-30s: %ld\n" ,"load" , cfs_rq->load.weight);#ifdef CONFIG_FAIR_GROUP_SCHED #ifdef CONFIG_SMP -SEQ_printf (m," .%-30s: %lu\n" ,"shares" , cfs_rq->shares); +SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"load_avg" , +SPLIT_NS (cfs_rq->load_avg)); +SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"load_period" , +SPLIT_NS (cfs_rq->load_period)); +SEQ_printf (m," .%-30s: %ld\n" ,"load_contrib" , + cfs_rq->load_contribution); +SEQ_printf (m," .%-30s: %d\n" ,"load_tg" , +atomic_read (&tg->load_weight));#endif +print_cfs_group_stats (m, cpu, cfs_rq->tg);#endif }
kernel/sched_fair.c +107 -57
264 lines not on this page · raw message
kernel/sched_features.h +0 -2
@@ -52,8 +52,6 @@ SCHED_FEAT(ARCH_POWER, 0) SCHED_FEAT(HRTICK, 0) SCHED_FEAT(DOUBLE_TICK, 0)SCHED_FEAT (LB_BIAS ,1 ) -SCHED_FEAT(LB_SHARES_UPDATE, 1) -SCHED_FEAT (ASYM_EFF_LOAD ,1 )/* * Spin-wait on mutex acquisition when the mutex owner is running on
kernel/sysctl.c +0 -19
@@ -259,8 +259,6 @@ static int min_wakeup_granularity_ns; /* 0 usecs */static int max_wakeup_granularity_ns =NSEC_PER_SEC ;/* 1 second */ static int min_sched_tunable_scaling =SCHED_TUNABLESCALING_NONE ;static int max_sched_tunable_scaling =SCHED_TUNABLESCALING_END -1 ; -static int min_sched_shares_ratelimit =100000 ;/* 100 usec */ -static int max_sched_shares_ratelimit =NSEC_PER_SEC ;/* 1 second */ #endif #ifdef CONFIG_COMPACTION
@@ -305,15 +303,6 @@ static struct ctl_table kern_table[] = { .extra2 = &max_wakeup_granularity_ns, }, { - .procname = "sched_shares_ratelimit", - .data = &sysctl_sched_shares_ratelimit, - .maxlen = sizeof(unsigned int), - .mode = 0644, - .proc_handler = sched_proc_update_handler, - .extra1 = &min_sched_shares_ratelimit, - .extra2 = &max_sched_shares_ratelimit, - }, - { .procname = "sched_tunable_scaling", .data = &sysctl_sched_tunable_scaling, .maxlen = sizeof(enum sched_tunable_scaling),
@@ -323,14 +312,6 @@ static struct ctl_table kern_table[] = { .extra2 = &max_sched_tunable_scaling, }, { - .procname = "sched_shares_thresh", - .data = &sysctl_sched_shares_thresh, - .maxlen = sizeof(unsigned int), - .mode = 0644, - .proc_handler = proc_dointvec_minmax, - .extra1 = &zero, - }, - { .procname = "sched_migration_cost", .data = &sysctl_sched_migration_cost, .maxlen = sizeof(unsigned int),
[tip:sched/core] sched: Implement on-demand (active) cfs_rq list
In reply to Paul TurnerCommit-ID: 3d4b47b4b040c9d77dd68104cfc1055d89a55afd Gitweb: http://git.kernel.org/tip/3d4b47b4b040c9d77dd68104cfc1055d89a55afd Author: Peter Zijlstra <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:01 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:47 +0100
sched: Implement on-demand (active) cfs_rq list
Make certain load-balance actions scale per number of active cgroups instead of the number of existing cgroups.
This makes wakeup/sleep paths more expensive, but is a win for systems where the vast majority of existing cgroups are idle.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 105 +++++++++++++------------------------------------- kernel/sched_fair.c | 46 +++++++++++++++++++--- kernel/sched_rt.c | 24 ++++++++++++ 3 files changed, 92 insertions(+), 83 deletions(-)
kernel/sched.c +28 -77
@@ -274,9 +274,7 @@ struct task_group {#define root_task_group init_task_group -/* task_group_lock serializes add/remove of task groups and also changes to -* a task group's cpu shares. -*/ +/* task_group_lock serializes the addition/removal of task groups */ static DEFINE_SPINLOCK (task_group_lock);#ifdef CONFIG_FAIR_GROUP_SCHED
@@ -344,6 +342,7 @@ struct cfs_rq {* leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This * list is used during load balance. */ +int on_list;struct list_head leaf_cfs_rq_list;struct task_group *tg;/* group that "owns" this runqueue */
@@ -1547,7 +1546,7 @@ static unsigned long cpu_avg_load_per_task(int cpu)#ifdef CONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_load (struct cfs_rq *cfs_rq,int lb);static void update_cfs_shares (struct cfs_rq *cfs_rq);/*
@@ -1570,7 +1569,7 @@ static int tg_shares_up(struct task_group *tg, void *data)raw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,1 ); load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); load_avg -= cfs_rq->load_contribution;
@@ -7688,15 +7687,13 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)#ifdef CONFIG_FAIR_GROUP_SCHED static void init_tg_cfs_entry (struct task_group *tg,struct cfs_rq *cfs_rq, -struct sched_entity *se,int cpu,int add, +struct sched_entity *se,int cpu,struct sched_entity *parent) {struct rq *rq =cpu_rq (cpu); tg->cfs_rq[cpu] = cfs_rq;init_cfs_rq (cfs_rq, rq); cfs_rq->tg = tg; -if (add) -list_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se;/* se could be NULL for init_task_group */
@@ -7716,7 +7713,7 @@ static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,#ifdef CONFIG_RT_GROUP_SCHED static void init_tg_rt_entry (struct task_group *tg,struct rt_rq *rt_rq, -struct sched_rt_entity *rt_se,int cpu,int add, +struct sched_rt_entity *rt_se,int cpu,struct sched_rt_entity *parent) {struct rq *rq =cpu_rq (cpu);
@@ -7725,8 +7722,6 @@ static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,init_rt_rq (rt_rq, rq); rt_rq->tg = tg; rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime; -if (add) -list_add (&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list); tg->rt_se[cpu] = rt_se;if (!rt_se)
@@ -7835,7 +7830,7 @@ void __init sched_init(void)* We achieve this by letting init_task_group's tasks sit * directly in rq->cfs (i.e init_task_group->se[] = NULL). */ -init_tg_cfs_entry (&init_task_group, &rq->cfs,NULL , i,1 ,NULL ); +init_tg_cfs_entry (&init_task_group, &rq->cfs,NULL , i,NULL );#endif #endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -7843,7 +7838,7 @@ void __init sched_init(void)#ifdef CONFIG_RT_GROUP_SCHED INIT_LIST_HEAD (&rq->leaf_rt_rq_list);#ifdef CONFIG_CGROUP_SCHED -init_tg_rt_entry (&init_task_group, &rq->rt,NULL , i,1 ,NULL ); +init_tg_rt_entry (&init_task_group, &rq->rt,NULL , i,NULL );#endif #endif
@@ -8119,7 +8114,7 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)if (!se) goto err_free_rq; -init_tg_cfs_entry (tg, cfs_rq, se, i,0 , parent->se[i]); +init_tg_cfs_entry (tg, cfs_rq, se, i, parent->se[i]); }return 1 ;
@@ -8130,15 +8125,22 @@ err: return 0; } -static inline void register_fair_sched_group (struct task_group *tg,int cpu) -{ -list_add_rcu (&tg->cfs_rq[cpu]->leaf_cfs_rq_list, - &cpu_rq (cpu)->leaf_cfs_rq_list); -} -static inline void unregister_fair_sched_group (struct task_group *tg,int cpu) { -list_del_rcu (&tg->cfs_rq[cpu]->leaf_cfs_rq_list); +struct rq *rq =cpu_rq (cpu); +unsigned long flags; +int i; + +/* +* Only empty task groups can be destroyed; so we can speculatively +* check on_list without danger of it being re-added. +*/ +if (!tg->cfs_rq[cpu]->on_list) +return ; + +raw_spin_lock_irqsave (&rq->lock, flags); +list_del_leaf_cfs_rq (tg->cfs_rq[i]); +raw_spin_unlock_irqrestore (&rq->lock, flags); }#else /* !CONFG_FAIR_GROUP_SCHED */ static inline void free_fair_sched_group (struct task_group *tg)
@@ -8151,10 +8153,6 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)return 1 ; } -static inline void register_fair_sched_group (struct task_group *tg,int cpu) -{ -} -static inline void unregister_fair_sched_group (struct task_group *tg,int cpu) { }
@@ -8209,7 +8207,7 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)if (!rt_se) goto err_free_rq; -init_tg_rt_entry (tg, rt_rq, rt_se, i,0 , parent->rt_se[i]); +init_tg_rt_entry (tg, rt_rq, rt_se, i, parent->rt_se[i]); }return 1 ;
@@ -8219,17 +8217,6 @@ err_free_rq: err: return 0; } - -static inline void register_rt_sched_group (struct task_group *tg,int cpu) -{ -list_add_rcu (&tg->rt_rq[cpu]->leaf_rt_rq_list, - &cpu_rq (cpu)->leaf_rt_rq_list); -} - -static inline void unregister_rt_sched_group (struct task_group *tg,int cpu) -{ -list_del_rcu (&tg->rt_rq[cpu]->leaf_rt_rq_list); -}#else /* !CONFIG_RT_GROUP_SCHED */ static inline void free_rt_sched_group (struct task_group *tg) {
@@ -8240,14 +8227,6 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent) {return 1 ; } - -static inline void register_rt_sched_group (struct task_group *tg,int cpu) -{ -} - -static inline void unregister_rt_sched_group (struct task_group *tg,int cpu) -{ -}#endif /* CONFIG_RT_GROUP_SCHED */ #ifdef CONFIG_CGROUP_SCHED
@@ -8263,7 +8242,6 @@ struct task_group *sched_create_group(struct task_group *parent) {struct task_group *tg;unsigned long flags; -int i; tg =kzalloc (sizeof (*tg),GFP_KERNEL );if (!tg)
@@ -8276,10 +8254,6 @@ struct task_group *sched_create_group(struct task_group *parent) goto err;spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) { -register_fair_sched_group (tg, i); -register_rt_sched_group (tg, i); - }list_add_rcu (&tg->list, &task_groups);WARN_ON (!parent);/* root should already exist */
@@ -8309,11 +8283,11 @@ void sched_destroy_group(struct task_group *tg)unsigned long flags;int i; -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) { +/* end participation in shares distribution */ +for_each_possible_cpu (i)unregister_fair_sched_group (tg, i); -unregister_rt_sched_group (tg, i); - } + +spin_lock_irqsave (&task_group_lock, flags);list_del_rcu (&tg->list);list_del_rcu (&tg->siblings);spin_unlock_irqrestore (&task_group_lock, flags);
@@ -8391,7 +8365,6 @@ static DEFINE_MUTEX(shares_mutex);int sched_group_set_shares (struct task_group *tg,unsigned long shares) {int i; -unsigned long flags;/* * We can't change the weight of the root cgroup.
@@ -8408,19 +8381,6 @@ int sched_group_set_shares(struct task_group *tg, unsigned long shares)if (tg->shares == shares) goto done; -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) -unregister_fair_sched_group (tg, i); -list_del_rcu (&tg->siblings); -spin_unlock_irqrestore (&task_group_lock, flags); - -/* wait for any ongoing reference to this group to finish */ -synchronize_sched (); - -/* -* Now we are free to modify the group's share on each cpu -* w/o tripping rebalance_share or load_balance_fair. -*/ tg->shares = shares;for_each_possible_cpu (i) {/*
@@ -8429,15 +8389,6 @@ int sched_group_set_shares(struct task_group *tg, unsigned long shares)set_se_shares (tg->se[i], shares); } -/* -* Enable load balance activity on this group, by inserting it back on -* each cpu's rq->leaf_cfs_rq_list. -*/ -spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) -register_fair_sched_group (tg, i); -list_add_rcu (&tg->siblings, &tg->parent->children); -spin_unlock_irqrestore (&task_group_lock, flags); done:mutex_unlock (&shares_mutex);return 0 ;
kernel/sched_fair.c +40 -6
106 lines not on this page · raw message
kernel/sched_rt.c +24 -0
@@ -183,6 +183,17 @@ static inline u64 sched_rt_period(struct rt_rq *rt_rq)return ktime_to_ns (rt_rq->tg->rt_bandwidth.rt_period); } +static inline void list_add_leaf_rt_rq (struct rt_rq *rt_rq) +{ +list_add_rcu (&rt_rq->leaf_rt_rq_list, + &rq_of_rt_rq (rt_rq)->leaf_rt_rq_list); +} + +static inline void list_del_leaf_rt_rq (struct rt_rq *rt_rq) +{ +list_del_rcu (&rt_rq->leaf_rt_rq_list); +} +#define for_each_leaf_rt_rq (rt_rq, rq) \ list_for_each_entry_rcu(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list)
@@ -276,6 +287,14 @@ static inline u64 sched_rt_period(struct rt_rq *rt_rq)return ktime_to_ns (def_rt_bandwidth.rt_period); } +static inline void list_add_leaf_rt_rq (struct rt_rq *rt_rq) +{ +} + +static inline void list_del_leaf_rt_rq (struct rt_rq *rt_rq) +{ +} +#define for_each_leaf_rt_rq (rt_rq, rq) \ for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL)
@@ -825,6 +844,9 @@ static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)if (group_rq && (rt_rq_throttled (group_rq) || !group_rq->rt_nr_running))return ; +if (!rt_rq->rt_nr_running) +list_add_leaf_rt_rq (rt_rq); +if (head)list_add (&rt_se->run_list, queue);else
@@ -844,6 +866,8 @@ static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)__clear_bit (rt_se_prio (rt_se), array->bitmap);dec_rt_tasks (rt_se, rt_rq); +if (!rt_rq->rt_nr_running) +list_del_leaf_rt_rq (rt_rq); }/*
[tip:sched/core] sched: Make tg_shares_up() walk on-demand
In reply to Paul TurnerCommit-ID: 9e3081ca61147b29f52fddb4f7c6b6b82ea5eb7a Gitweb: http://git.kernel.org/tip/9e3081ca61147b29f52fddb4f7c6b6b82ea5eb7a Author: Peter Zijlstra <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:02 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:47 +0100
sched: Make tg_shares_up() walk on-demand
Make tg_shares_up() use the active cgroup list, this means we cannot do a strict bottom-up walk of the hierarchy, but assuming its a very wide tree with a small number of active groups it should be a win.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 67 --------------------------------------------------- kernel/sched_fair.c | 58 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 insertions(+), 67 deletions(-)
kernel/sched.c +0 -67
@@ -279,13 +279,6 @@ static DEFINE_SPINLOCK(task_group_lock);#ifdef CONFIG_FAIR_GROUP_SCHED -#ifdef CONFIG_SMP -static int root_task_group_empty (void ) -{ -return list_empty (&root_task_group.children); -} -#endif -# define INIT_TASK_GROUP_LOAD NICE_0_LOAD/*
@@ -1546,48 +1539,6 @@ static unsigned long cpu_avg_load_per_task(int cpu)#ifdef CONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq,int lb); -static void update_cfs_shares (struct cfs_rq *cfs_rq); - -/* -* update tg->load_weight by folding this cpu's load_avg -*/ -static int tg_shares_up (struct task_group *tg,void *data) -{ -long load_avg; -struct cfs_rq *cfs_rq; -unsigned long flags; -int cpu = (long )data; -struct rq *rq; - -if (!tg->se[cpu]) -return 0 ; - - rq =cpu_rq (cpu); - cfs_rq = tg->cfs_rq[cpu]; - -raw_spin_lock_irqsave (&rq->lock, flags); - -update_rq_clock (rq); -update_cfs_load (cfs_rq,1 ); - - load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); - load_avg -= cfs_rq->load_contribution; - -atomic_add (load_avg, &tg->load_weight); - cfs_rq->load_contribution += load_avg; - -/* -* We need to update shares after updating tg->load_weight in -* order to adjust the weight of groups with long running tasks. -*/ -update_cfs_shares (cfs_rq); - -raw_spin_unlock_irqrestore (&rq->lock, flags); - -return 0 ; -} -/* * Compute the cpu's hierarchical load factor for each task group. * This needs to be done in a top-down fashion because the load of a child
@@ -1611,29 +1562,11 @@ static int tg_load_down(struct task_group *tg, void *data) return 0; } -static void update_shares (long cpu) -{ -if (root_task_group_empty ()) -return ; - -/* -* XXX: replace with an on-demand list -*/ - -walk_tg_tree (tg_nop, tg_shares_up, (void *)cpu); -} -static void update_h_load (long cpu) {walk_tg_tree (tg_load_down, tg_nop, (void *)cpu); } -#else - -static inline void update_shares (int cpu) -{ -} -#endif #ifdef CONFIG_PREEMPT
kernel/sched_fair.c +58 -0
70 lines not on this page · raw message
[tip:sched/core] sched: Fix load corruption from update_cfs_shares()
In reply to Paul TurnerCommit-ID: f0d7442a5924a802b66eef79b3708f77297bfb35 Gitweb: http://git.kernel.org/tip/f0d7442a5924a802b66eef79b3708f77297bfb35 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:03 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:47 +0100
sched: Fix load corruption from update_cfs_shares()
As part of enqueue_entity both a new entity weight and its contribution to the queuing cfs_rq / rq are updated. Since update_cfs_shares will only update the queueing weights when the entity is on_rq (which in this case it is not yet), there's a dependency loop here:
update_cfs_shares needs account_entity_enqueue to update cfs_rq->load.weight account_entity_enqueue needs the updated weight for the queuing cfs_rq load[*]
Fix this and avoid spurious dequeue/enqueues by issuing update_cfs_shares as if we had accounted the enqueue already.
This was also resulting in rq->load corruption previously.
[*]: this dependency also exists when using the group cfs_rq w/
update_cfs_shares as the weight of the enqueued entity changes without the load being updated.
LKML-Reference: <[email protected]>
--- kernel/sched_fair.c | 16 ++++++++-------- 1 files changed, 8 insertions(+), 8 deletions(-)
kernel/sched_fair.c +8 -8
@@ -718,7 +718,7 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,account_entity_enqueue (cfs_rq, se); } -static void update_cfs_shares (struct cfs_rq *cfs_rq) +static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta) {struct task_group *tg;struct sched_entity *se;
@@ -732,7 +732,7 @@ static void update_cfs_shares(struct cfs_rq *cfs_rq)if (!se)return ; - load = cfs_rq->load.weight; + load = cfs_rq->load.weight + weight_delta; load_weight =atomic_read (&tg->load_weight); load_weight -= cfs_rq->load_contribution;
@@ -754,7 +754,7 @@ static inline void update_cfs_load(struct cfs_rq *cfs_rq, int lb) { } -static inline void update_cfs_shares (struct cfs_rq *cfs_rq) +static inline void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta) { }#endif /* CONFIG_FAIR_GROUP_SCHED */
@@ -881,8 +881,8 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)*/ update_curr (cfs_rq);update_cfs_load (cfs_rq,0 ); +update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se); -update_cfs_shares (cfs_rq);if (flags &ENQUEUE_WAKEUP ) {place_entity (cfs_rq, se,0 );
@@ -944,7 +944,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)update_cfs_load (cfs_rq,0 );account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 );/* * Normalize the entity after updating the min_vruntime because the
@@ -1177,7 +1177,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct cfs_rq *cfs_rq =cfs_rq_of (se);update_cfs_load (cfs_rq,0 ); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 ); }hrtick_update (rq);
@@ -1207,7 +1207,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)struct cfs_rq *cfs_rq =cfs_rq_of (se);update_cfs_load (cfs_rq,0 ); -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 ); }hrtick_update (rq);
@@ -2034,7 +2034,7 @@ static int tg_shares_up(struct task_group *tg, int cpu)* We need to update shares after updating tg->load_weight in * order to adjust the weight of groups with long running tasks. */ -update_cfs_shares (cfs_rq); +update_cfs_shares (cfs_rq,0 );raw_spin_unlock_irqrestore (&rq->lock, flags);
[tip:sched/core] sched: Fix update_cfs_load() synchronization
In reply to Paul TurnerCommit-ID: e33078baa4d30ad1d0e46d1f62b9e5a63a3e6ee3 Gitweb: http://git.kernel.org/tip/e33078baa4d30ad1d0e46d1f62b9e5a63a3e6ee3 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:04 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:48 +0100
sched: Fix update_cfs_load() synchronization
Using cfs_rq->nr_running is not sufficient to synchronize update_cfs_load with the put path since nr_running accounting occurs at deactivation.
It's also not safe to make the removal decision based on load_avg as this fails with both high periods and low shares. Resolve this by clipping history after 4 periods without activity.
Note: the above will always occur from update_shares() since in the last-task-sleep-case that task will still be cfs_rq->curr when update_cfs_load is called.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 2 +- kernel/sched_fair.c | 33 +++++++++++++++++++++------------ 2 files changed, 22 insertions(+), 13 deletions(-)
kernel/sched.c +1 -1
@@ -355,7 +355,7 @@ struct cfs_rq {u64 load_avg;u64 load_period; -u64 load_stamp; +u64 load_stamp, load_last;unsigned long load_contribution;#endif
kernel/sched_fair.c +21 -12
@@ -674,10 +674,11 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) }#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq,int lb) +static void update_cfs_load (struct cfs_rq *cfs_rq) {u64 period =sched_avg_period ();u64 now, delta; +unsigned long load = cfs_rq->load.weight;if (!cfs_rq)return ;
@@ -685,9 +686,19 @@ static void update_cfs_load(struct cfs_rq *cfs_rq, int lb) now =rq_of (cfs_rq)->clock; delta = now - cfs_rq->load_stamp; +/* truncate load history at 4 idle periods */ +if (cfs_rq->load_stamp > cfs_rq->load_last && + now - cfs_rq->load_last >4 * period) { + cfs_rq->load_period =0 ; + cfs_rq->load_avg =0 ; + } + cfs_rq->load_stamp = now; cfs_rq->load_period += delta; - cfs_rq->load_avg += delta * cfs_rq->load.weight; +if (load) { + cfs_rq->load_last = now; + cfs_rq->load_avg += delta * load; + }while (cfs_rq->load_period > period) {/*
@@ -700,10 +711,8 @@ static void update_cfs_load(struct cfs_rq *cfs_rq, int lb) cfs_rq->load_avg /=2 ; } -if (lb && !cfs_rq->nr_running) { -if (cfs_rq->load_avg < (period /8 )) -list_del_leaf_cfs_rq (cfs_rq); - } +if (!cfs_rq->curr && !cfs_rq->nr_running && !cfs_rq->load_avg) +list_del_leaf_cfs_rq (cfs_rq); } static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
@@ -750,7 +759,7 @@ static void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta) reweight_entity(cfs_rq_of(se), se, shares); }#else /* CONFIG_FAIR_GROUP_SCHED */ -static inline void update_cfs_load (struct cfs_rq *cfs_rq,int lb) +static inline void update_cfs_load (struct cfs_rq *cfs_rq) { }
@@ -880,7 +889,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se);
@@ -941,7 +950,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (se != cfs_rq->curr)__dequeue_entity (cfs_rq, se); se->on_rq =0 ; -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq);update_cfs_shares (cfs_rq,0 );
@@ -1176,7 +1185,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq,0 ); }
@@ -1206,7 +1215,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq,0 ); +update_cfs_load (cfs_rq);update_cfs_shares (cfs_rq,0 ); }
@@ -2023,7 +2032,7 @@ static int tg_shares_up(struct task_group *tg, int cpu)raw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq,1 ); +update_cfs_load (cfs_rq); load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); load_avg -= cfs_rq->load_contribution;
[tip:sched/core] sched: Introduce hierarchal order on shares update list
In reply to Paul TurnerCommit-ID: 67e86250f8ea7b8f7da53ac25ea73c6bd71f5cd9 Gitweb: http://git.kernel.org/tip/67e86250f8ea7b8f7da53ac25ea73c6bd71f5cd9 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:05 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:48 +0100
sched: Introduce hierarchal order on shares update list
Avoid duplicate shares update calls by ensuring children always appear before parents in rq->leaf_cfs_rq_list.
This allows us to do a single in-order traversal for update_shares().
Since we always enqueue in bottom-up order this reduces to 2 cases:
1) Our parent is already in the list, e.g.
root
\
b
/\
c d* (root->b->c already enqueued)Since d's parent is enqueued we push it to the head of the list, implicitly ahead of b.
2) Our parent does not appear in the list (or we have no parent)
In this case we enqueue to the tail of the list, if our parent is subsequently enqueued (bottom-up) it will appear to our right by the same rule.
LKML-Reference: <[email protected]>
--- kernel/sched_fair.c | 26 ++++++++++++++++---------- 1 files changed, 16 insertions(+), 10 deletions(-)
kernel/sched_fair.c +16 -10
@@ -146,8 +146,20 @@ static inline struct cfs_rq *cpu_cfs_rq(struct cfs_rq *cfs_rq, int this_cpu)static inline void list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq) {if (!cfs_rq->on_list) { -list_add_rcu (&cfs_rq->leaf_cfs_rq_list, +/* +* 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. +*/ +if (cfs_rq->tg->parent && + cfs_rq->tg->parent->cfs_rq[cpu_of (rq_of (cfs_rq))]->on_list) { +list_add_rcu (&cfs_rq->leaf_cfs_rq_list, + &rq_of (cfs_rq)->leaf_cfs_rq_list); + }else { +list_add_tail_rcu (&cfs_rq->leaf_cfs_rq_list, &rq_of (cfs_rq)->leaf_cfs_rq_list); + } cfs_rq->on_list =1 ; }
@@ -2016,7 +2028,7 @@ out:/* * update tg->load_weight by folding this cpu's load_avg */ -static int tg_shares_up (struct task_group *tg,int cpu) +static int update_shares_cpu (struct task_group *tg,int cpu) {struct cfs_rq *cfs_rq;unsigned long flags;
@@ -2056,14 +2068,8 @@ static void update_shares(int cpu)struct rq *rq =cpu_rq (cpu);rcu_read_lock (); -for_each_leaf_cfs_rq (rq, cfs_rq) { -struct task_group *tg = cfs_rq->tg; - -do { -tg_shares_up (tg, cpu); - tg = tg->parent; - }while (tg); - } +for_each_leaf_cfs_rq (rq, cfs_rq) +update_shares_cpu (cfs_rq->tg, cpu);rcu_read_unlock (); }
[tip:sched/core] sched: Add sysctl_sched_shares_window
In reply to Paul TurnerCommit-ID: a7a4f8a752ec734b2eab904fc863d5dc873de338 Gitweb: http://git.kernel.org/tip/a7a4f8a752ec734b2eab904fc863d5dc873de338 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:06 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:49 +0100
sched: Add sysctl_sched_shares_window
Introduce a new sysctl for the shares window and disambiguate it from sched_time_avg.
A 10ms window appears to be a good compromise between accuracy and performance.
LKML-Reference: <[email protected]>
--- include/linux/sched.h | 1 + kernel/sched_fair.c | 9 ++++++++- kernel/sysctl.c | 7 +++++++ 3 files changed, 16 insertions(+), 1 deletions(-)
include/linux/sched.h +1 -0
@@ -1900,6 +1900,7 @@ extern unsigned int sysctl_sched_migration_cost;extern unsigned int sysctl_sched_nr_migrate;extern unsigned int sysctl_sched_time_avg;extern unsigned int sysctl_timer_migration; +extern unsigned int sysctl_sched_shares_window; int sched_proc_update_handler(struct ctl_table *table, int write, void __user *buffer, size_t *length,
kernel/sched_fair.c +8 -1
@@ -89,6 +89,13 @@ unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL; const_debug unsigned int sysctl_sched_migration_cost = 500000UL; +/* +* The exponential sliding window over which load is averaged for shares +* distribution. +* (default: 10msec) +*/ +unsigned int __read_mostly sysctl_sched_shares_window =10000000UL ; +static const struct sched_class fair_sched_class;/**************************************************************
@@ -688,7 +695,7 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED static void update_cfs_load (struct cfs_rq *cfs_rq) { -u64 period =sched_avg_period (); +u64 period = sysctl_sched_shares_window;u64 now, delta;unsigned long load = cfs_rq->load.weight;
kernel/sysctl.c +7 -0
@@ -333,6 +333,13 @@ static struct ctl_table kern_table[] = { .proc_handler = proc_dointvec, }, { + .procname = "sched_shares_window", + .data = &sysctl_sched_shares_window, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = proc_dointvec, + }, + { .procname = "timer_migration", .data = &sysctl_timer_migration, .maxlen = sizeof(unsigned int),
[tip:sched/core] sched: Update shares on idle_balance
In reply to Paul TurnerCommit-ID: c66eaf619c0c7937e9ded160ae83b5a7a6b19b56 Gitweb: http://git.kernel.org/tip/c66eaf619c0c7937e9ded160ae83b5a7a6b19b56 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:07 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:49 +0100
sched: Update shares on idle_balance
Since shares updates are no longer expensive and effectively local, update them at idle_balance(). This allows us to more quickly redistribute shares to another cpu when our load becomes idle.
LKML-Reference: <[email protected]>
--- kernel/sched_fair.c | 1 + 1 files changed, 1 insertions(+), 0 deletions(-)
kernel/sched_fair.c +1 -0
@@ -3343,6 +3343,7 @@ static void idle_balance(int this_cpu, struct rq *this_rq)*/ raw_spin_unlock (&this_rq->lock); +update_shares (this_cpu);for_each_domain (this_cpu, sd) {unsigned long interval;int balance =1 ;
[tip:sched/core] sched: Implement demand based update_cfs_load()
In reply to Paul TurnerCommit-ID: 3b3d190ec3683d568fd2ebaead5e1ec7f97b6e37 Gitweb: http://git.kernel.org/tip/3b3d190ec3683d568fd2ebaead5e1ec7f97b6e37 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:08 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:49 +0100
sched: Implement demand based update_cfs_load()
When the system is busy, dilation of rq->next_balance makes lb->update_shares() insufficiently frequent for threads which don't sleep (no dequeue/enqueue updates). Adjust for this by making demand based updates based on the accumulation of execution time sufficient to wrap our averaging window.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 9 ++++++++- kernel/sched_fair.c | 12 ++++++++++++ 2 files changed, 20 insertions(+), 1 deletions(-)
kernel/sched.c +8 -1
@@ -353,9 +353,16 @@ struct cfs_rq {*/ unsigned long h_load; +/* +* Maintaining per-cpu shares distribution for group scheduling +* +* load_stamp is the last time we updated the load average +* load_last is the last time we updated the load average and saw load +* load_unacc_exec_time is currently unaccounted execution time +*/ u64 load_avg;u64 load_period; -u64 load_stamp, load_last; +u64 load_stamp, load_last, load_unacc_exec_time;unsigned long load_contribution;#endif
kernel/sched_fair.c +12 -0
@@ -539,6 +539,9 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)return calc_delta_fair (sched_slice (cfs_rq, se), se); } +static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta); +/* * Update the current task's runtime statistics. Skip current tasks that * are not in our scheduling class.
@@ -558,6 +561,14 @@ __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, curr->vruntime += delta_exec_weighted;update_min_vruntime (cfs_rq); + +#ifdef CONFIG_FAIR_GROUP_SCHED + cfs_rq->load_unacc_exec_time += delta_exec; +if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) { +update_cfs_load (cfs_rq); +update_cfs_shares (cfs_rq,0 ); + } +#endif }static void update_curr (struct cfs_rq *cfs_rq)
@@ -713,6 +724,7 @@ static void update_cfs_load(struct cfs_rq *cfs_rq) } cfs_rq->load_stamp = now; + cfs_rq->load_unacc_exec_time =0 ; cfs_rq->load_period += delta;if (load) { cfs_rq->load_last = now;
[tip:sched/core] sched: Allow update_cfs_load() to update global load
In reply to Paul TurnerCommit-ID: d6b5591829bd348a5fbe1c428d28dea00621cdba Gitweb: http://git.kernel.org/tip/d6b5591829bd348a5fbe1c428d28dea00621cdba Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:09 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:50 +0100
sched: Allow update_cfs_load() to update global load
Refactor the global load updates from update_shares_cpu() so that update_cfs_load() can update global load when it is more than ~10% out of sync.
The new global_load parameter allows us to force an update, regardless of the error factor so that we can synchronize w/ update_shares().
LKML-Reference: <[email protected]>
--- kernel/sched_fair.c | 44 +++++++++++++++++++++++++++++--------------- 1 files changed, 29 insertions(+), 15 deletions(-)
kernel/sched_fair.c +29 -15
@@ -539,7 +539,7 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)return calc_delta_fair (sched_slice (cfs_rq, se), se); } -static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update);static void update_cfs_shares (struct cfs_rq *cfs_rq,long weight_delta);/*
@@ -565,7 +565,7 @@ __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,#ifdef CONFIG_FAIR_GROUP_SCHED cfs_rq->load_unacc_exec_time += delta_exec;if (cfs_rq->load_unacc_exec_time > sysctl_sched_shares_window) { -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }#endif
@@ -704,7 +704,22 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) }#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED -static void update_cfs_load (struct cfs_rq *cfs_rq) +static void update_cfs_rq_load_contribution (struct cfs_rq *cfs_rq, +int global_update) +{ +struct task_group *tg = cfs_rq->tg; +long load_avg; + + load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); + load_avg -= cfs_rq->load_contribution; + +if (global_update ||abs (load_avg) > cfs_rq->load_contribution /8 ) { +atomic_add (load_avg, &tg->load_weight); + cfs_rq->load_contribution += load_avg; + } +} + +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update) {u64 period = sysctl_sched_shares_window;u64 now, delta;
@@ -731,6 +746,11 @@ static void update_cfs_load(struct cfs_rq *cfs_rq) cfs_rq->load_avg += delta * load; } +/* consider updating load contribution on each fold or truncate */ +if (global_update || cfs_rq->load_period > period + || !cfs_rq->load_period) +update_cfs_rq_load_contribution (cfs_rq, global_update); +while (cfs_rq->load_period > period) {/* * Inline assembly required to prevent the compiler
@@ -790,7 +810,7 @@ static void update_cfs_shares(struct cfs_rq *cfs_rq, long weight_delta) reweight_entity(cfs_rq_of(se), se, shares); }#else /* CONFIG_FAIR_GROUP_SCHED */ -static inline void update_cfs_load (struct cfs_rq *cfs_rq) +static void update_cfs_load (struct cfs_rq *cfs_rq,int global_update) { }
@@ -920,7 +940,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq, se->load.weight);account_entity_enqueue (cfs_rq, se);
@@ -981,7 +1001,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (se != cfs_rq->curr)__dequeue_entity (cfs_rq, se); se->on_rq =0 ; -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );account_entity_dequeue (cfs_rq, se);update_min_vruntime (cfs_rq);update_cfs_shares (cfs_rq,0 );
@@ -1216,7 +1236,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }
@@ -1246,7 +1266,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)for_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -update_cfs_load (cfs_rq); +update_cfs_load (cfs_rq,0 );update_cfs_shares (cfs_rq,0 ); }
@@ -2052,7 +2072,6 @@ static int update_shares_cpu(struct task_group *tg, int cpu)struct cfs_rq *cfs_rq;unsigned long flags;struct rq *rq; -long load_avg;if (!tg->se[cpu])return 0 ;
@@ -2063,12 +2082,7 @@ static int update_shares_cpu(struct task_group *tg, int cpu)raw_spin_lock_irqsave (&rq->lock, flags);update_rq_clock (rq); -update_cfs_load (cfs_rq); - - load_avg =div64_u64 (cfs_rq->load_avg, cfs_rq->load_period+1 ); - load_avg -= cfs_rq->load_contribution; -atomic_add (load_avg, &tg->load_weight); - cfs_rq->load_contribution += load_avg; +update_cfs_load (cfs_rq,1 );/* * We need to update shares after updating tg->load_weight in
[tip:sched/core] sched: Update tg->shares after cpu.shares write
In reply to Paul TurnerCommit-ID: 9437178f623a19af5951808d880a8599f66ac150 Gitweb: http://git.kernel.org/tip/9437178f623a19af5951808d880a8599f66ac150 Author: Paul Turner <[email protected]> AuthorDate: Mon, 15 Nov 2010 15:47:10 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 18 Nov 2010 13:27:50 +0100
sched: Update tg->shares after cpu.shares write
Formerly sched_group_set_shares would force a rebalance by overflowing domain share sums. Now that per-cpu averages are maintained we can set the true value by issuing an update_cfs_shares() following a tg->shares update.
Also initialize tg se->load to 0 for consistency since we'll now set correct weights on enqueue.
LKML-Reference: <[email protected]>
--- kernel/sched.c | 42 +++++++++++------------------------------- 1 files changed, 11 insertions(+), 31 deletions(-)
kernel/sched.c +11 -31
@@ -7646,7 +7646,7 @@ static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq, se->cfs_rq = parent->my_q; se->my_q = cfs_rq; -update_load_set (&se->load, tg->shares); +update_load_set (&se->load,0 ); se->parent = parent; }#endif
@@ -8274,37 +8274,12 @@ void sched_move_task(struct task_struct *tsk)#endif /* CONFIG_CGROUP_SCHED */ #ifdef CONFIG_FAIR_GROUP_SCHED -static void __set_se_shares (struct sched_entity *se,unsigned long shares) -{ -struct cfs_rq *cfs_rq = se->cfs_rq; -int on_rq; - - on_rq = se->on_rq; -if (on_rq) -dequeue_entity (cfs_rq, se,0 ); - -update_load_set (&se->load, shares); - -if (on_rq) -enqueue_entity (cfs_rq, se,0 ); -} - -static void set_se_shares (struct sched_entity *se,unsigned long shares) -{ -struct cfs_rq *cfs_rq = se->cfs_rq; -struct rq *rq = cfs_rq->rq; -unsigned long flags; - -raw_spin_lock_irqsave (&rq->lock, flags); -__set_se_shares (se, shares); -raw_spin_unlock_irqrestore (&rq->lock, flags); -} -static DEFINE_MUTEX (shares_mutex);int sched_group_set_shares (struct task_group *tg,unsigned long shares) {int i; +unsigned long flags;/* * We can't change the weight of the root cgroup.
@@ -8323,10 +8298,15 @@ int sched_group_set_shares(struct task_group *tg, unsigned long shares) tg->shares = shares;for_each_possible_cpu (i) { -/* -* force a rebalance -*/ -set_se_shares (tg->se[i], shares); +struct rq *rq =cpu_rq (i); +struct sched_entity *se; + + se = tg->se[i]; +/* Propagate contribution to hierarchy */ +raw_spin_lock_irqsave (&rq->lock, flags); +for_each_sched_entity (se) +update_cfs_shares (group_cfs_rq (se),0 ); +raw_spin_unlock_irqrestore (&rq->lock, flags); } done: