reducing overhead for tg->shares distribution
PATCH v2 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(-)
sched.c renamed from sched.c.orig +11 -31
@@ -7575,7 +7575,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
@@ -8194,37 +8194,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.
@@ -8243,10 +8218,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 v2 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 | 10 ++++++++++ 2 files changed, 18 insertions(+), 1 deletion(-)
sched.c renamed from sched.c.orig +8 -1
@@ -355,9 +355,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
sched_fair.c renamed from sched_fair.c.orig +10 -0
@@ -538,6 +538,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.
@@ -557,6 +560,12 @@ __update_curr(struct cfs_rq *cfs_rq, str curr->vruntime += delta_exec_weighted;update_min_vruntime (cfs_rq); + + 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 ); + } }static void update_curr (struct cfs_rq *cfs_rq)
@@ -712,6 +721,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 v2 2/11 sched: on-demand (active) cfs_rq list
In reply to Paul TurnerFrom: 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 | 86 +++++++++------------------------------------------- kernel/sched_fair.c | 46 ++++++++++++++++++++++++--- kernel/sched_rt.c | 24 ++++++++++++++ 3 files changed, 79 insertions(+), 77 deletions(-)
sched.c renamed from sched.c.orig +15 -71
@@ -344,6 +344,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 */
@@ -1530,7 +1531,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);/*
@@ -1553,7 +1554,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;
@@ -7622,15 +7623,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 */
@@ -7650,7 +7649,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);
@@ -7659,8 +7658,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)
@@ -7769,7 +7766,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 */
@@ -7777,7 +7774,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
@@ -8053,7 +8050,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 ;
@@ -8084,14 +8081,6 @@ int alloc_fair_sched_group(struct task_g {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) -{ -}#endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_RT_GROUP_SCHED
@@ -8143,7 +8132,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 ;
@@ -8153,17 +8142,6 @@ int alloc_rt_sched_group(struct task_gro 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) {
@@ -8174,14 +8152,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
@@ -8197,7 +8167,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)
@@ -8210,10 +8179,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 */
@@ -8244,10 +8209,12 @@ void sched_destroy_group(struct task_groint i;spin_lock_irqsave (&task_group_lock, flags); -for_each_possible_cpu (i) { -unregister_fair_sched_group (tg, i); -unregister_rt_sched_group (tg, i); - } +/* +* XXX should not be a race against enqueue, even without rq->lock +* because only empty groups can be destroyed. +*/ +for_each_possible_cpu (i) +list_del_leaf_cfs_rq (tg->cfs_rq[i]);list_del_rcu (&tg->list);list_del_rcu (&tg->siblings);spin_unlock_irqrestore (&task_group_lock, flags);
@@ -8325,7 +8292,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.
@@ -8342,19 +8308,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) {/*
@@ -8363,15 +8316,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 ;
sched_fair.c renamed from sched_fair.c.orig +40 -6
106 lines not on this page · raw message
sched_rt.c renamed from sched_rt.c.orig +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 v2 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(-)
sched_fair.c renamed from sched_fair.c.orig +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);
@@ -2030,7 +2030,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 v2 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 | 17 ---- 6 files changed, 162 insertions(+), 211 deletions(-)
linux/sched.h renamed from linux/sched.h.orig +0 -2
@@ -1868,8 +1868,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 {
sched.c renamed from sched.c.orig +44 -129
278 lines not on this page · raw message
sched_debug.c renamed from sched_debug.c.orig +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 }
sched_fair.c renamed from sched_fair.c.orig +107 -57
264 lines not on this page · raw message
sched_features.h renamed from sched_features.h.orig +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
sysctl.c renamed from sysctl.c.orig +0 -17
@@ -307,15 +307,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),
@@ -325,14 +316,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),
PATCH v2 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(-)
sched_fair.c renamed from sched_fair.c.orig +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;
linux/sched.h renamed from linux/sched.h.orig +1 -0
@@ -1883,6 +1883,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,
sysctl.c renamed from sysctl.c.orig +7 -0
@@ -337,6 +337,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 v2 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 at 8 foldings.
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(-)
sched_fair.c renamed from sched_fair.c.orig +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 ); }
@@ -2019,7 +2028,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;
sched.c renamed from sched.c.orig +1 -1
@@ -357,7 +357,7 @@ struct cfs_rq {u64 load_avg;u64 load_period; -u64 load_stamp; +u64 load_stamp, load_last;unsigned long load_contribution;#endif
v2 cover reducing overhead for tg->shares distribution
This is v2 of the tg_shares_up re-write previously posted at:
http://lkml.org/lkml/2010/10/16/17
The key idea behind this patchset is an idea of Peter Zijlstra to compute global loads as a function of local averages avoiding the cpu-cpu interactions which previously plagued tg_shares_up.
Not much 'material' has changed since v1 since results seem favourable/stable. The only functional change is a bug fix in the wake_affine path where the v1 was using the waking task's group shares at all levels instead of the per-level task_group.
Changes:
sched-rework-tg_shares_up.patch
- 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 v2 10/11 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().
--- kernel/sched_fair.c | 42 ++++++++++++++++++++++++++++-------------- 1 file changed, 28 insertions(+), 14 deletions(-)
sched_fair.c renamed from sched_fair.c.orig +28 -14
@@ -538,7 +538,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);/*
@@ -563,7 +563,7 @@ __update_curr(struct cfs_rq *cfs_rq, str 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 ); } }
@@ -701,7 +701,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;
@@ -728,6 +743,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
@@ -917,7 +937,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);
@@ -978,7 +998,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 );
@@ -1213,7 +1233,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 ); }
@@ -1243,7 +1263,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 ); }
@@ -2045,7 +2065,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 ;
@@ -2056,12 +2075,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 v2 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(+)
sched_fair.c renamed from sched_fair.c.orig +1 -0
@@ -3301,6 +3301,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 v2 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(-)
sched_fair.c renamed from sched_fair.c.orig +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 ; }
@@ -2009,7 +2021,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;
@@ -2049,14 +2061,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 v2 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(-)
sched.c renamed from sched.c.orig +0 -67
@@ -281,13 +281,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/*
@@ -1531,48 +1524,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
@@ -1596,29 +1547,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
sched_fair.c renamed from sched_fair.c.orig +58 -0
70 lines not on this page · raw message
Re: [tg_shares_up rewrite v2 10/11] sched: allow update_cfs_load to update global load
In reply to Paul TurnerFrom: Paul Turner <[email protected]>
Date: Wed, 10 Nov 2010 19:50:15 -0800
Quoted 7 lines
Refactor the global load updates from
update_shares_cpu()so thatupdate_cfs_load()can update global load when it is more than ~10% out of sync.The new
global_loadparameter allows us to force an update, regardless of the error factor so that we can synchronize w/update_shares().Signed-off-by Paul Turner <[email protected]>
This patch breaks the build, you didn't update the arguments of update_cfs_load() in the !CONFIG_FAIR_GROUP_SCHED case.
Re: [tg_shares_up rewrite v2 10/11] sched: allow update_cfs_load to update global load
From: David Miller <[email protected]>
Date: Wed, 10 Nov 2010 20:47:04 -0800 (PST)
Quoted 6 lines
From: Paul Turner <[email protected]>
Date: Wed, 10 Nov 2010 19:50:15 -0800Quoted 3 lines
Refactor the global load updates from
update_shares_cpu()so thatupdate_cfs_load()can update global load when it is more than ~10% out of sync.
Quoted 7 lines
Quoted 4 lines
The new
global_loadparameter allows us to force an update, regardless of the error factor so that we can synchronize w/update_shares().Signed-off-by Paul Turner <[email protected]>This patch breaks the build, you didn't update the arguments of
update_cfs_load()in the !CONFIG_FAIR_GROUP_SCHED case.
And even with this fixed there are even larger problems, as you're making access to structure members such as 'load_unacc_exec_time' which only exist when CONFIG_FAIR_GROUP_SCHED is set, but you're doing it in code that is built unconditionally.
Please fix all of these build problems, as I want to test your changes without all of the group scheduler bloat turned on.
Thanks.
Re: [tg_shares_up rewrite v2 10/11] sched: allow update_cfs_load to update global load
Ah, I should have checked that, sorry.
I've fixed these errors for a v3. But in fixing them I've realized I think we have a race in sched_destroy_group() (in patch 2/11).
While it's true that we are safe for a subsequent enqueue in the same group, we're not protected against a list element being removed due to decay in the update shares path. Or from a another group being enqueued (via wake-up).
Might as well fix this at the same time so I'll fix it and send out in the morning.
Thanks!
Quoted 27 lines · David Miller
From: David Miller <[email protected]>
Date: Wed, 10 Nov 2010 20:47:04 -0800 (PST)Quoted 6 lines
From: Paul Turner <[email protected]>
Date: Wed, 10 Nov 2010 19:50:15 -0800Quoted 3 lines
Refactor the global load updates from
update_shares_cpu()so thatupdate_cfs_load()can update global load when it is more than ~10% out of sync.Quoted 7 lines
Quoted 4 lines
The new
global_loadparameter allows us to force an update, regardless of the error factor so that we can synchronize w/update_shares().Signed-off-by Paul Turner <[email protected]>This patch breaks the build, you didn't update the arguments of
update_cfs_load()in the !CONFIG_FAIR_GROUP_SCHED case.And even with this fixed there are even larger problems, as you're making access to structure members such as '
load_unacc_exec_time' which only exist whenCONFIG_FAIR_GROUP_SCHEDis set, but you're doing it in code that is built unconditionally.Please fix all of these build problems, as I want to test your changes without all of the group scheduler bloat turned on.
Thanks.
Re: [tg_shares_up rewrite v2 10/11] sched: allow update_cfs_load to update global load
In reply to David MillerQuoted 2 lines · David Miller
Please fix all of these build problems, as I want to test your changes without all of the group scheduler bloat turned on.
Won't do much good though, this patch-set is fixing a pure group scheduler problem.