Reducing cost of tg->shares distribution
cover Reducing cost of tg->shares distribution
Hi all,
Peter previously posted a patchset that attempted to improve the problem of task_group share distribution. This is something that has been a long-time pain point for group scheduling. The existing algorithm considers distributions on a per-cpu-per-domain basis and carries a fairly high update overhead, especially on larger machines.
I was previously looking at improving this using Fenwick trees to allow a single sum without the exorbitant cost but then Peter's idea above was better :).
The kernel is that by monitoring the average contribution to load on a per-cpu-per-taskgroup basis we can distribute the weight for which we are expected to consume.
This set extends the original posting with a focus on increased fairness and reduced convergence (to true average) time. In particular the case of large over-commit in the case of a distributed wake-up is a concern which is now fairly well addressed.
Obviously everything's experimental but it should be stable/fair.
Some motivation:
24 thread intel box, 150 active cgroups, multiple threads/group, load at ~90% (10 second sample):
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_sharesSome fairness coverage for the above at: http://rs5.risingnet.net/~pjt/patches/shares_data_v1.txt
Note: The last patch is fairly obviously a temporary debug patch, I only include it as it interfaces with some analysis scripts I'm simultaneously trying to publish for the purposes of validating this series. Since this approach estimates the share distribution, the spread between issued shares and target is an important factor until people are happy with the patchset
Paul
TODO:
- Validate any RT interaction
- Continue collecting/analyzing performance and fairness data
- Should the shares period just be the sched_latency?
RFC 1/12 sched: rewrite tg_shares_up
From: 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 ]
--- include/linux/sched.h | 2 kernel/sched.c | 173 ++++++++++++------------------------------------ kernel/sched_debug.c | 15 +++- kernel/sched_fair.c | 166 +++++++++++++++++++++++++++++----------------- kernel/sched_features.h | 2 kernel/sysctl.c | 17 ---- 6 files changed, 163 insertions(+), 212 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 +108 -58
265 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),
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
Quoted 126 lines · On Fri, Oct 15, 2010 at 09:43:50PM -0700, [email protected] wrote:
From: Peter Zijlstra <[email protected]>
By tracking a per-cpu load-avg for each
cfs_rqand folding it into a globaltask_groupload on each tick we can reworktg_shares_upto be strictly per-cpu.This should improve cpu-cgroup performance for smp systems significantly.
[ Paul: changed to use queueing
cfs_rq]Signed-off-by Peter Zijlstra <[email protected]>Signed-off-by Paul Turner <[email protected]>Index:
kernel/sched_fair.c
===================================================================sched_fair.c renamed from sched_fair.c.orig +81
-3@@ -417,7 +417,6 @@ int sched_proc_update_handler(struct ctlWRT_SYSCTL (sched_min_granularity);WRT_SYSCTL (sched_latency);WRT_SYSCTL (sched_wakeup_granularity); -WRT_SYSCTL (sched_shares_ratelimit);#undef WRT_SYSCTLreturn 0 ;@@ -633,7 +632,6 @@ account_entity_enqueue(struct cfs_rq *cflist_add (&se->group_node, &cfs_rq->tasks); } cfs_rq->nr_running++; - se->on_rq =1 ; } static void@@ -647,9 +645,89 @@ account_entity_dequeue(struct cfs_rq *cflist_del_init (&se->group_node); } cfs_rq->nr_running--; - se->on_rq =0 ; } +#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED +static void update_cfs_load (struct cfs_rq *cfs_rq) +{ +u64 period =sched_avg_period (); +u64 now, delta; + +if (!cfs_rq) +return ; + + now =rq_of (cfs_rq)->clock; + delta = now - cfs_rq->load_stamp; + + cfs_rq->load_stamp = now; + cfs_rq->load_period += delta; + cfs_rq->load_avg += delta * cfs_rq->load.weight; + +while (cfs_rq->load_period > period) { +/* +* Inline assembly required to prevent the compiler +* optimising this loop into a divmod call. +* See __iter_div_u64_rem() for another example of this. +*/ + asm("" :"+rm" (cfs_rq->load_period)); + cfs_rq->load_period /=2 ; + cfs_rq->load_avg /=2 ; + } +} + +static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se, +unsigned long weight) +{ +if (se->on_rq) +account_entity_dequeue (cfs_rq, se); + +update_load_set (&se->load, weight); + +if (se->on_rq) +account_entity_enqueue (cfs_rq, se); +} + +static void update_cfs_shares (struct cfs_rq *cfs_rq) +{ +struct task_group *tg; +struct sched_entity *se; +long load_weight, load, shares; + +if (!cfs_rq) +return ; + + tg = cfs_rq->tg; + se = tg->se[cpu_of (rq_of (cfs_rq))]; +if (!se) +return ; + + load = cfs_rq->load.weight; + + load_weight =atomic_read (&tg->load_weight); + load_weight -= cfs_rq->load_contribution; + load_weight += load; + + shares = (tg->shares * load); +if (load_weight) + shares /= load_weight; + +if (shares <MIN_SHARES ) + shares =MIN_SHARES ; +if (shares > tg->shares) + shares = tg->shares; + +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 inline void update_cfs_shares (struct cfs_rq *cfs_rq) +{ +} +#endif /* CONFIG_FAIR_GROUP_SCHED */ +static void enqueue_sleeper (struct cfs_rq *cfs_rq,struct sched_entity *se) {#ifdef CONFIG_SCHEDSTATS
sched_fair.c enqueue_entity(struct cfs_rq *cfs_rq, st · line 853
Quoted 5 lines
sched_fair.c renamed from sched_fair.c.orig +1
-0@@ -771,7 +849,9 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); +update_cfs_load (cfs_rq);account_entity_enqueue (cfs_rq, se);
By placing update_cfs_load() before account_entity_enqueue(), you are updating cfs_rq->load_avg before actually taking into account the current load increment due to enqueing. I see same in dequeue also. Is there a reason for this ?
sched_fair.c enqueue_entity(struct cfs_rq *cfs_rq, st · line 854
Quoted 1 line
sched_fair.c renamed from sched_fair.c.orig +1
-0+update_cfs_shares (cfs_rq_of (se));
Isn't cfs_rq_of(se) same as cfs_rq that enqueue_entity() gets from enqueue_task_fair() ? Same for dequeue case.
Regards,
Bharata.
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
Quoted 129 lines · Bharata B Rao
Quoted 128 lines · On Fri, Oct 15, 2010 at 09:43:50PM -0700, [email protected] wrote:
From: Peter Zijlstra <[email protected]>
By tracking a per-cpu load-avg for each
cfs_rqand folding it into a globaltask_groupload on each tick we can reworktg_shares_upto be strictly per-cpu.This should improve cpu-cgroup performance for smp systems significantly.
[ Paul: changed to use queueing
cfs_rq]Signed-off-by Peter Zijlstra <[email protected]>Signed-off-by Paul Turner <[email protected]>Index:
kernel/sched_fair.c
===================================================================sched_fair.c renamed from sched_fair.c.orig +0
-2@@ -417,7 +417,6 @@ int sched_proc_update_handler(struct ctl WRT_SYSCTL(sched_min_granularity); WRT_SYSCTL(sched_latency); WRT_SYSCTL(sched_wakeup_granularity); - WRT_SYSCTL(sched_shares_ratelimit); #undef WRT_SYSCTL return 0;@@ -633,7 +632,6 @@ account_entity_enqueue(struct cfs_rq *cf list_add(&se->group_node, &cfs_rq->tasks); } cfs_rq->nr_running++; - se->on_rq = 1; }static void
sched_fair.c renamed from sched_fair.c.orig +81
-1@@ -647,9 +645,89 @@ account_entity_dequeue(struct cfs_rq *cf list_del_init(&se->group_node); } cfs_rq->nr_running--; - se->on_rq = 0; } +#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED +static void update_cfs_load (struct cfs_rq *cfs_rq) +{ + u64 period = sched_avg_period(); + u64 now, delta; + + if (!cfs_rq) + return; + + now = rq_of(cfs_rq)->clock; + delta = now - cfs_rq->load_stamp; + + cfs_rq->load_stamp = now; + cfs_rq->load_period += delta; + cfs_rq->load_avg += delta * cfs_rq->load.weight; + + while (cfs_rq->load_period > period) { + /* + * Inline assembly required to prevent the compiler + * optimising this loop into a divmod call. + * See __iter_div_u64_rem() for another example of this. + */ + asm("" : "+rm" (cfs_rq->load_period)); + cfs_rq->load_period /= 2; + cfs_rq->load_avg /= 2; + } +} + +static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se, + unsigned long weight) +{ + if (se->on_rq) + account_entity_dequeue(cfs_rq, se); + + update_load_set(&se->load, weight); + + if (se->on_rq) + account_entity_enqueue(cfs_rq, se); +} + +static void update_cfs_shares (struct cfs_rq *cfs_rq) +{ + struct task_group *tg; + struct sched_entity *se; + long load_weight, load, shares; + + if (!cfs_rq) + return; + + tg = cfs_rq->tg; + se = tg->se[cpu_of(rq_of(cfs_rq))]; + if (!se) + return; + + load = cfs_rq->load.weight; + + load_weight = atomic_read(&tg->load_weight); + load_weight -= cfs_rq->load_contribution; + load_weight += load; + + shares = (tg->shares * load); + if (load_weight) + shares /= load_weight; + + if (shares < MIN_SHARES) + shares = MIN_SHARES; + if (shares > tg->shares) + shares = tg->shares; + + 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 inline void update_cfs_shares (struct cfs_rq *cfs_rq) +{ +} +#endif /* CONFIG_FAIR_GROUP_SCHED */ + static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se) { #ifdef CONFIG_SCHEDSTATS@@ -771,7 +849,9 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */
Quoted 8 lines
sched_fair.c enqueue_entity(struct cfs_rq *cfs_rq, st · line 853
Quoted 3 lines
sched_fair.c renamed from sched_fair.c.orig +1
-0update_curr(cfs_rq); + update_cfs_load(cfs_rq); account_entity_enqueue(cfs_rq, se);By placing
update_cfs_load()beforeaccount_entity_enqueue(), you are updatingcfs_rq->load_avgbefore actually taking into account the current load increment due to enqueing. I see same in dequeue also. Is there a reason for this ?
Yes -- the update covers the interval spanning the previous update (tracked with load_stamp) and the present. This interval occurred prior to the above weight delta which will only be meaningful against the _next_ interval we account.
Quoted 6 lines
sched_fair.c enqueue_entity(struct cfs_rq *cfs_rq, st · line 854
Quoted 2 lines
sched_fair.c renamed from sched_fair.c.orig +1
-0+ update_cfs_shares(cfs_rq_of(se));Isn't
cfs_rq_of(se)same ascfs_rqthatenqueue_entity()gets fromenqueue_task_fair()? Same for dequeue case.
Yup.. no need for it, will fix.
Thanks
Quoted 3 lines
Regards,
Bharata.
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
In reply to [email protected]Quoted 26 lines · On Fri, Oct 15, 2010 at 09:43:50PM -0700, [email protected] wrote:
From: Peter Zijlstra <[email protected]>
sched_fair.c renamed from sched_fair.c.orig +0
-3@@ -417,7 +417,6 @@ int sched_proc_update_handler(struct ctlWRT_SYSCTL (sched_min_granularity);WRT_SYSCTL (sched_latency);WRT_SYSCTL (sched_wakeup_granularity); -WRT_SYSCTL (sched_shares_ratelimit);#undef WRT_SYSCTLreturn 0 ;@@ -633,7 +632,6 @@ account_entity_enqueue(struct cfs_rq *cflist_add (&se->group_node, &cfs_rq->tasks); } cfs_rq->nr_running++; - se->on_rq =1 ; } static void@@ -647,9 +645,89 @@ account_entity_dequeue(struct cfs_rq *cflist_del_init (&se->group_node); } cfs_rq->nr_running--; - se->on_rq =0 ; }
<snip>
Quoted 19 lines
sched_fair.c renamed from sched_fair.c.orig +3
-0@@ -771,7 +849,9 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr (cfs_rq); +update_cfs_load (cfs_rq);account_entity_enqueue (cfs_rq, se); +update_cfs_shares (cfs_rq_of (se));if (flags &ENQUEUE_WAKEUP ) {place_entity (cfs_rq, se,0 );@@ -782,6 +862,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, stcheck_spread (cfs_rq, se);if (se != cfs_rq->curr)__enqueue_entity (cfs_rq, se); + se->on_rq =1 ; }static void __clear_buddies (struct cfs_rq *cfs_rq,struct sched_entity *se)
sched_fair.c dequeue_entity(struct cfs_rq *cfs_rq, st · line 909
Quoted 4 lines
sched_fair.c renamed from sched_fair.c.orig +1
-0@@ -825,8 +906,11 @@ dequeue_entity(struct cfs_rq *cfs_rq, stif (se != cfs_rq->curr)__dequeue_entity (cfs_rq, se); + se->on_rq =0 ;
Since setting and un-setting of se->on_rq is completely handled within sched_fair.c, we can remove the redundant setting and un-setting of se->on_rq from sched.c:[en]dequeue_task. Even w/o this patch, they were redundant I suppose.
Regards,
Bharata.
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
Quoted 48 lines · Bharata B Rao
Quoted 26 lines · On Fri, Oct 15, 2010 at 09:43:50PM -0700, [email protected] wrote:
From: Peter Zijlstra <[email protected]>
sched_fair.c renamed from sched_fair.c.orig +0
-2@@ -417,7 +417,6 @@ int sched_proc_update_handler(struct ctl WRT_SYSCTL(sched_min_granularity); WRT_SYSCTL(sched_latency); WRT_SYSCTL(sched_wakeup_granularity); - WRT_SYSCTL(sched_shares_ratelimit); #undef WRT_SYSCTL return 0;@@ -633,7 +632,6 @@ account_entity_enqueue(struct cfs_rq *cf list_add(&se->group_node, &cfs_rq->tasks); } cfs_rq->nr_running++; - se->on_rq = 1; }static void
sched_fair.c renamed from sched_fair.c.orig +0
-1@@ -647,9 +645,89 @@ account_entity_dequeue(struct cfs_rq *cf list_del_init(&se->group_node); } cfs_rq->nr_running--; - se->on_rq = 0; }<snip>
Quoted 20 lines
sched_fair.c renamed from sched_fair.c.orig +3
-0@@ -771,7 +849,9 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr(cfs_rq); + update_cfs_load(cfs_rq); account_entity_enqueue(cfs_rq, se); + update_cfs_shares(cfs_rq_of(se)); if (flags & ENQUEUE_WAKEUP) { place_entity(cfs_rq, se, 0);@@ -782,6 +862,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st check_spread(cfs_rq, se); if (se != cfs_rq->curr) __enqueue_entity(cfs_rq, se); + se->on_rq = 1; } static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)@@ -825,8 +906,11 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
Quoted 8 lines
sched_fair.c dequeue_entity(struct cfs_rq *cfs_rq, st · line 909
Quoted 3 lines
sched_fair.c renamed from sched_fair.c.orig +1
-0if (se != cfs_rq->curr) __dequeue_entity(cfs_rq, se); + se->on_rq = 0;Since setting and un-setting of
se->on_rqis completely handled withinsched_fair.c, we can remove the redundant setting and un-setting ofse->on_rqfrom sched.c:[en]dequeue_task. Even w/o this patch, they were redundant I suppose.
Mmmm I think SCHED_RT (currently) depends on this, it could probably cleaned up in a separate patch.
Quoted 4 lines
Regards,
Bharata.
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
In reply to Bharata B RaoQuoted 6 lines · Bharata B Rao
Quoted 1 line
+
se->on_rq= 0;Since setting and un-setting of
se->on_rqis completely handled withinsched_fair.c, we can remove the redundant setting and un-setting ofse->on_rqfrom sched.c:[en]dequeue_task. Even w/o this patch, they were redundant I suppose.
sadly not, sched_rt.c also uses them. It really shouldn't live in sched_entity but in a common set.
I've long wanted to rework all that into something like:
struct sched_entity {
/* common fields */
union {
struct sched_fair_entity fair;
struct sched_rt_entity rt;
};};
But that never quite happened.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [RFC tg_shares_up improvements - v1 01/12] sched: rewrite tg_shares_up
[resend due to html formatting creeping into first email]
Quoted 590 lines · Paul Turner
Quoted 587 lines · On Sat, Oct 16, 2010 at 12:43 AM, <[email protected]> wrote:
From: Peter Zijlstra <[email protected]>
By tracking a per-cpu load-avg for each
cfs_rqand folding it into a globaltask_groupload on each tick we can reworktg_shares_upto be strictly per-cpu.This should improve cpu-cgroup performance for smp systems significantly.
[ Paul: changed to use queueing
cfs_rq]Signed-off-by Peter Zijlstra <[email protected]>Signed-off-by Paul Turner <[email protected]>---
include/linux/sched.h | 2
kernel/sched.c | 173 ++++++++++++------------------------------------kernel/sched_debug.c| 15 +++-
kernel/sched_fair.c | 166 +++++++++++++++++++++++++++++-----------------kernel/sched_features.h| 2
kernel/sysctl.c | 17 ----6 files changed, 163 insertions(+), 212 deletions(-)Index:
include/linux/sched.h
===================================================================linux/sched.h renamed from linux/sched.h.orig +0
-2@@ -1868,8 +1868,6 @@ static inline void wake_up_idle_cpu(int 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 {Index:
kernel/sched.c
===================================================================sched.c renamed from sched.c.orig +44
-129@@ -253,6 +253,8 @@ struct task_group { /* runqueue "owned" by this group on each cpu */ struct cfs_rq **cfs_rq; unsigned long shares; + + atomic_t load_weight; #endif #ifdef CONFIG_RT_GROUP_SCHED@@ -359,15 +361,11 @@ struct cfs_rq {*/ unsigned long h_load; - /* - * this cpu's part of tg->shares - */ - unsigned long shares; + u64 load_avg; + u64 load_period; + u64 load_stamp; - /* - * load.weight at the time we set shares - */ - unsigned long rq_weight; + unsigned long load_contribution; #endif #endif };@@ -790,20 +788,6 @@ late_initcall(sched_init_debug); const_debug unsigned int sysctl_sched_nr_migrate = 32; /* -* ratelimit for updating the group shares. -* default: 0.25ms -*/ -unsigned int sysctl_sched_shares_ratelimit =250000 ; -unsigned int normalized_sysctl_sched_shares_ratelimit =250000 ; - -/* -* Inject some fuzzyness into changing the per-cpu group shares -* this avoids remote rq-locks at the expense of fairness. -* default: 4 -*/ -unsigned int sysctl_sched_shares_thresh =4 ; - -/* * period over which we average the RT time consumption, measured * in ms. * @@ -1352,6 +1336,12 @@ static inline void update_load_sub(struc lw->inv_weight = 0; } +static inline void update_load_set (struct load_weight *lw,unsigned long w) +{ + lw->weight = w; + lw->inv_weight = 0; +} + /** To aid in avoiding the subversion of "niceness" due to uneven distribution * of tasks with abnormal "nice" values across CPUs the contribution that @@ -1540,97 +1530,44 @@ static unsigned long cpu_avg_load_per_ta #ifdef CONFIG_FAIR_GROUP_SCHED -static __read_mostly unsigned long __percpu *update_shares_data; - -static void __set_se_shares (struct sched_entity *se,unsigned long shares); - -/* -* Calculate and set the cpu's group shares. -*/ -static void update_group_shares_cpu (struct task_group *tg,int cpu, - unsigned long sd_shares, - unsigned long sd_rq_weight, - unsigned long *usd_rq_weight) -{ - unsigned long shares, rq_weight; - int boost = 0; - - rq_weight = usd_rq_weight[cpu]; - if (!rq_weight) { - boost = 1; - rq_weight = NICE_0_LOAD; - } - - /* - * \Sum_j shares_j * rq_weight_i - * shares_i = ----------------------------- - * \Sum_j rq_weight_j - */ - shares = (sd_shares * rq_weight) / sd_rq_weight; - shares = clamp_t(unsigned long, shares, MIN_SHARES, MAX_SHARES); - - if (abs(shares - tg->se[cpu]->load.weight) > - sysctl_sched_shares_thresh) { - struct rq *rq = cpu_rq(cpu); - unsigned long flags; - - raw_spin_lock_irqsave(&rq->lock, flags); - tg->cfs_rq[cpu]->rq_weight = boost ? 0 : rq_weight; - tg->cfs_rq[cpu]->shares = boost ? 0 : shares; - __set_se_shares(tg->se[cpu], shares); - raw_spin_unlock_irqrestore(&rq->lock, flags); - } -} +static void update_cfs_load (struct cfs_rq *cfs_rq); +static void update_cfs_shares (struct cfs_rq *cfs_rq); /* - * Re-compute the task group their per cpu shares over the given domain. - * This needs to be done in a bottom-up fashion because the rq weight of a - * parent group depends on the shares of its child groups. + * update tg->load_weight by folding this cpu's load_avg */ static int tg_shares_up(struct task_group *tg, void *data) { - unsigned long weight, rq_weight = 0, sum_weight = 0, shares = 0; - unsigned long *usd_rq_weight; - struct sched_domain *sd = data; + long load_avg; + struct cfs_rq *cfs_rq; unsigned long flags; - int i; + int cpu = (long)data; + struct rq *rq; - if (!tg->se[0]) + if (!tg->se[cpu]) return 0; - local_irq_save(flags); - usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id()); - - for_each_cpu(i, sched_domain_span(sd)) { - weight = tg->cfs_rq[i]->load.weight; - usd_rq_weight[i] = weight; - - rq_weight += weight; - /* - * If there are currently no tasks on the cpu pretend there - * is one of average load so that when a new task gets to - * run here it will not get delayed by group starvation. - */ - if (!weight) - weight = NICE_0_LOAD; + rq = cpu_rq(cpu); + cfs_rq = tg->cfs_rq[cpu]; - sum_weight += weight; - shares += tg->cfs_rq[i]->shares; - } + raw_spin_lock_irqsave(&rq->lock, flags); - if (!rq_weight) - rq_weight = sum_weight; + update_rq_clock(rq); + update_cfs_load(cfs_rq); - if ((!shares && rq_weight) || shares > tg->shares) - shares = tg->shares; + load_avg = div64_u64(cfs_rq->load_avg, cfs_rq->load_period+1); + load_avg -= cfs_rq->load_contribution; - if (!sd->parent || !(sd->parent->flags & SD_LOAD_BALANCE)) - shares = tg->shares; + atomic_add(load_avg, &tg->load_weight); + cfs_rq->load_contribution += load_avg; - for_each_cpu(i, sched_domain_span(sd)) - update_group_shares_cpu(tg, i, shares, rq_weight, usd_rq_weight); + /* + * 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); - local_irq_restore(flags); + raw_spin_unlock_irqrestore(&rq->lock, flags); return 0; }@@ -1649,7 +1586,7 @@ static int tg_load_down(struct task_grou load = cpu_rq(cpu)->load.weight; } else { load = tg->parent->cfs_rq[cpu]->h_load; - load *= tg->cfs_rq[cpu]->shares; + load *= tg->se[cpu]->load.weight; load /= tg->parent->cfs_rq[cpu]->load.weight + 1; }@@ -1658,21 +1595,16 @@ static int tg_load_down(struct task_grou return 0; } -static void update_shares (struct sched_domain *sd) +static void update_shares (long cpu) { - s64 elapsed; - u64 now; - if (root_task_group_empty()) return; - now = local_clock(); - elapsed = now - sd->last_update; + /* + * XXX: replace with an on-demand list + */ - if (elapsed >= (s64)(u64)sysctl_sched_shares_ratelimit) { - sd->last_update = now; - walk_tg_tree(tg_nop, tg_shares_up, sd); - } + walk_tg_tree(tg_nop, tg_shares_up, (void *)cpu); } static void update_h_load(long cpu)@@ -1682,7 +1614,7 @@ static void update_h_load(long cpu) #else -static inline void update_shares (struct sched_domain *sd) +static inline void update_shares (int cpu) { }@@ -1807,15 +1739,6 @@ static void double_rq_unlock(struct rq * #endif -#ifdef CONFIG_FAIR_GROUP_SCHED -static void cfs_rq_set_shares (struct cfs_rq *cfs_rq,unsigned long shares) -{ -#ifdef CONFIG_SMP - cfs_rq->shares = shares; -#endif -} -#endif - static void calc_load_account_idle(struct rq *this_rq); static void update_sysctl(void); static int get_update_sysctl_factor(void);@@ -5404,7 +5327,6 @@ static void update_sysctl(void) SET_SYSCTL(sched_min_granularity); SET_SYSCTL(sched_latency); SET_SYSCTL(sched_wakeup_granularity); - SET_SYSCTL(sched_shares_ratelimit); #undef SET_SYSCTL }@@ -7721,8 +7643,7 @@ static void init_tg_cfs_entry(struct tas se->cfs_rq = parent->my_q; se->my_q = cfs_rq; - se->load.weight = tg->shares; - se->load.inv_weight = 0; + update_load_set(&se->load, tg->shares); se->parent = parent; } #endif@@ -7815,10 +7736,6 @@ void __init sched_init(void) #endif /* CONFIG_CGROUP_SCHED */ -#if definedCONFIG_FAIR_GROUP_SCHED && definedCONFIG_SMP - update_shares_data = __alloc_percpu(nr_cpu_ids * sizeof(unsigned long), - __alignof__(unsigned long)); -#endif for_each_possible_cpu(i) { struct rq *rq;@@ -8386,8 +8303,7 @@ static void __set_se_shares(struct sched if (on_rq) dequeue_entity(cfs_rq, se, 0); - se->load.weight = shares; - se->load.inv_weight = 0; + update_load_set(&se->load, shares); if (on_rq) enqueue_entity(cfs_rq, se, 0);@@ -8444,7 +8360,6 @@ int sched_group_set_shares(struct task_g /* * force a rebalance */ - cfs_rq_set_shares(tg->cfs_rq[i], 0); set_se_shares(tg->se[i], shares); }Index:
kernel/sched_debug.c
===================================================================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 }Index:
kernel/sched_fair.c
===================================================================sched_fair.c renamed from sched_fair.c.orig +0
-2@@ -417,7 +417,6 @@ int sched_proc_update_handler(struct ctl WRT_SYSCTL(sched_min_granularity); WRT_SYSCTL(sched_latency); WRT_SYSCTL(sched_wakeup_granularity); - WRT_SYSCTL(sched_shares_ratelimit); #undef WRT_SYSCTL return 0;@@ -633,7 +632,6 @@ account_entity_enqueue(struct cfs_rq *cf list_add(&se->group_node, &cfs_rq->tasks); } cfs_rq->nr_running++; - se->on_rq = 1; }static void
sched_fair.c renamed from sched_fair.c.orig +103
-33@@ -647,9 +645,89 @@ account_entity_dequeue(struct cfs_rq *cf list_del_init(&se->group_node); } cfs_rq->nr_running--; - se->on_rq = 0; } +#if definedCONFIG_SMP && definedCONFIG_FAIR_GROUP_SCHED +static void update_cfs_load (struct cfs_rq *cfs_rq) +{ + u64 period = sched_avg_period(); + u64 now, delta; + + if (!cfs_rq) + return; + + now = rq_of(cfs_rq)->clock; + delta = now - cfs_rq->load_stamp; + + cfs_rq->load_stamp = now; + cfs_rq->load_period += delta; + cfs_rq->load_avg += delta * cfs_rq->load.weight; + + while (cfs_rq->load_period > period) { + /* + * Inline assembly required to prevent the compiler + * optimising this loop into a divmod call. + * See __iter_div_u64_rem() for another example of this. + */ + asm("" : "+rm" (cfs_rq->load_period)); + cfs_rq->load_period /= 2; + cfs_rq->load_avg /= 2; + } +} + +static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se, + unsigned long weight) +{ + if (se->on_rq) + account_entity_dequeue(cfs_rq, se); + + update_load_set(&se->load, weight); + + if (se->on_rq) + account_entity_enqueue(cfs_rq, se); +} + +static void update_cfs_shares (struct cfs_rq *cfs_rq) +{ + struct task_group *tg; + struct sched_entity *se; + long load_weight, load, shares; + + if (!cfs_rq) + return; + + tg = cfs_rq->tg; + se = tg->se[cpu_of(rq_of(cfs_rq))]; + if (!se) + return; + + load = cfs_rq->load.weight; + + load_weight = atomic_read(&tg->load_weight); + load_weight -= cfs_rq->load_contribution; + load_weight += load; + + shares = (tg->shares * load); + if (load_weight) + shares /= load_weight; + + if (shares < MIN_SHARES) + shares = MIN_SHARES; + if (shares > tg->shares) + shares = tg->shares; + + 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 inline void update_cfs_shares (struct cfs_rq *cfs_rq) +{ +} +#endif /* CONFIG_FAIR_GROUP_SCHED */ + static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se) { #ifdef CONFIG_SCHEDSTATS@@ -771,7 +849,9 @@ enqueue_entity(struct cfs_rq *cfs_rq, st* Update run-time statistics of the 'current'. */ update_curr(cfs_rq); + update_cfs_load(cfs_rq); account_entity_enqueue(cfs_rq, se); + update_cfs_shares(cfs_rq_of(se)); if (flags & ENQUEUE_WAKEUP) { place_entity(cfs_rq, se, 0);@@ -782,6 +862,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st check_spread(cfs_rq, se); if (se != cfs_rq->curr) __enqueue_entity(cfs_rq, se); + se->on_rq = 1; } static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)@@ -825,8 +906,11 @@ dequeue_entity(struct cfs_rq *cfs_rq, st if (se != cfs_rq->curr) __dequeue_entity(cfs_rq, se); + se->on_rq = 0; + update_cfs_load(cfs_rq); account_entity_dequeue(cfs_rq, se); update_min_vruntime(cfs_rq); + update_cfs_shares(cfs_rq_of(se)); /** Normalize the entity after updating the min_vruntime because the @@ -1055,6 +1139,13 @@ enqueue_task_fair(struct rq *rq, struct flags = ENQUEUE_WAKEUP; } + for_each_sched_entity(se) { + struct cfs_rq *cfs_rq = cfs_rq_of(se); + + update_cfs_load(cfs_rq); + update_cfs_shares(cfs_rq); + } + hrtick_update(rq); }@@ -1071,12 +1162,20 @@ static void dequeue_task_fair(struct rq for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); dequeue_entity(cfs_rq, se, flags); + /* Don't dequeue parent if it has other entities besides us */ if (cfs_rq->load.weight) break; flags |= DEQUEUE_SLEEP; } + for_each_sched_entity(se) { + struct cfs_rq *cfs_rq = cfs_rq_of(se); + + update_cfs_load(cfs_rq); + update_cfs_shares(cfs_rq); + } + hrtick_update(rq); }@@ -1143,51 +1242,20 @@ static void task_waking_fair(struct rq ** Adding load to a group doesn't make a group heavier, but can cause movement * of group shares between cpus. Assuming the shares were perfectly aligned one * can calculate the shift in shares. -* -* The problem is that perfectly aligning the shares is rather expensive, hence -* we try to avoid doing that too often - see update_shares(), which ratelimits -* this change. -* -* We compensate this by not only taking the current delta into account, but -* also considering the delta between when the shares were last adjusted and -* now. -* -* We still saw a performance dip, some tracing learned us that between -* cgroup:/ and cgroup:/foo balancing the number of affine wakeups increased -* significantly. Therefore try to bias the error in direction of failing -* the affine wakeup. -* */ -static long effective_load (struct task_group *tg,int cpu, - long wl, long wg) +static long effective_load (struct task_group *tg,int cpu,long wl,long wg) { struct sched_entity *se = tg->se[cpu]; if (!tg->parent) return wl; - /* - * By not taking the decrease of shares on the other cpu into - * account our error leans towards reducing the affine wakeups. - */ - if (!wl && sched_feat(ASYM_EFF_LOAD)) - return wl; - for_each_sched_entity(se) { long S, rw, s, a, b; - long more_w; - - /* - * Instead of using this increment, also add the difference - * between when the shares were last updated and now. - */ - more_w = se->my_q->load.weight - se->my_q->rq_weight; - wl += more_w; - wg += more_w;
Quoted 5 lines
sched_fair.c static void task_waking_fair(struct rq * · line 1256
Quoted 4 lines
sched_fair.c renamed from sched_fair.c.orig +1
-3- S = se->my_q->tg->shares; - s = se->my_q->shares; - rw = se->my_q->rq_weight; + S = tg->shares;
This needs to at least be se->my_q->tg->shares (versus tg->shares as we walk up the tree).
Quoted 4 lines
sched_fair.c static void task_waking_fair(struct rq * · line 1258
Quoted 3 lines
sched_fair.c renamed from sched_fair.c.orig +2
-0+ s = se->load.weight; + rw = se->my_q->load.weight;
I suspect we could get better accuracy if we used the new knowledge of global weight more directly (which we can get from the load_contribution without having to bounce tg->load_weight around).
This path needs some attention in general though so I'll leave such musings to a second patchset which will focus on improving group wake_affine behavior.
Quoted 107 lines
Quoted 106 lines
sched_fair.c renamed from sched_fair.c.orig +0
-17a = S*(rw + wl); b = S*rw + s*wg;@@ -1508,23 +1576,6 @@ select_task_rq_fair(struct rq *rq, struc sd = tmp; } -#ifdef CONFIG_FAIR_GROUP_SCHED - if (sched_feat(LB_SHARES_UPDATE)) { - /* - * Pick the largest domain to update shares over - */ - tmp = sd; - if (affine_sd && (!tmp || affine_sd->span_weight > sd->span_weight)) - tmp = affine_sd; - - if (tmp) { - raw_spin_unlock(&rq->lock); - update_shares(tmp); - raw_spin_lock(&rq->lock); - } - } -#endif - if (affine_sd) { if (cpu == prev_cpu || wake_affine(affine_sd, p, sync)) return select_idle_sibling(p, cpu);@@ -2977,7 +3028,6 @@ static int load_balance(int this_cpu, st schedstat_inc(sd, lb_count[idle]);redo:
-update_shares(sd);
group =find_busiest_group(sd, this_cpu, &imbalance, idle, &sd_idle, cpus, balance);sched_fair.c renamed from sched_fair.c.orig +0
-0@@ -3119,8 +3169,6 @@ out_one_pinned:else
ld_moved = 0;
out:
- if (ld_moved)
-update_shares(sd);
returnld_moved;
}sched_fair.c renamed from sched_fair.c.orig +2
-0@@ -3514,6 +3562,8 @@ static void rebalance_domains(int cpu, e int update_next_balance = 0; int need_serialize; + update_shares(cpu); + for_each_domain(cpu, sd) { if (!(sd->flags & SD_LOAD_BALANCE)) continue;Index:
kernel/sched_features.h
===================================================================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 Index:
kernel/sysctl.c
===================================================================sysctl.c renamed from sysctl.c.orig +0
-18@@ -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), --
RFC 2/12 sched: on-demand (active) cfs_rq list
In reply to [email protected]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 | 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); }/*
RFC 3/12 sched: make tg_shares_up() walk on-demand
In reply to [email protected]From: 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
RFC 4/12 sched: fix load corruption from update_cfs_shares
In reply to [email protected]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.
--- 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_of (se), se->load.weight);account_entity_enqueue (cfs_rq, se); -update_cfs_shares (cfs_rq_of (se));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_of (se)); +update_cfs_shares (cfs_rq_of (se),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);
RFC 5/12 sched: fix update_cfs_load synchronization
In reply to [email protected]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 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_of (se), 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_of (se),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
Re: [RFC tg_shares_up improvements - v1 05/12] sched: fix update_cfs_load synchronization
Quoted 7 lines · On Fri, Oct 15, 2010 at 09:43:54PM -0700, [email protected] wrote:
Using
cfs_rq->nr_runningis not sufficient to synchronizeupdate_cfs_loadwith the put path sincenr_runningaccounting occurs at deactivation.It's also not safe to make the removal decision based on
load_avgas this fails with both high periods and low shares. Resolve this by clipping history at 8 foldings.
Did you mean 4 foldings (and not 8) above since I see you are truncating the load history at 4 idle periods ?
Quoted 33 lines
sched_fair.c renamed from sched_fair.c.orig +13
-5@@ -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); }
Re: [RFC tg_shares_up improvements - v1 05/12] sched: fix update_cfs_load synchronization
Quoted 11 lines · Bharata B Rao
Quoted 7 lines · On Fri, Oct 15, 2010 at 09:43:54PM -0700, [email protected] wrote:
Using
cfs_rq->nr_runningis not sufficient to synchronizeupdate_cfs_loadwith the put path sincenr_runningaccounting occurs at deactivation.It's also not safe to make the removal decision based on
load_avgas this fails with both high periods and low shares. Resolve this by clipping history at 8 foldings.Did you mean 4 foldings (and not 8) above since I see you are truncating the load history at 4 idle periods ?
We end up folding every period/2 (after the first fold) since after that we start at period/2 and not 0.
Thus, if we were issuing 'continuous' load updates triggering this condition would mean that we had folded idle periods into our load_avg 8 times.
Granted, it's possible for there to be less folds given sporadic load updates so I'll just update the comment to reference periods.
Thanks
Quoted 36 lines
Quoted 35 lines
sched_fair.c renamed from sched_fair.c.orig +13
-5@@ -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); }
RFC 6/12 sched: hierarchal order on shares update list
In reply to [email protected]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.
--- 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 (); }
RFC 7/12 sched: add sysctl_sched_shares_window
In reply to [email protected]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.
--- include/linux/sched.h | 1 + kernel/sched_fair.c | 8 +++++++- kernel/sysctl.c | 7 +++++++ 3 files changed, 15 insertions(+), 1 deletion(-)
sched_fair.c renamed from sched_fair.c.orig +7 -1
@@ -89,6 +89,12 @@ unsigned int normalized_sysctl_sched_wak const_debug unsigned int sysctl_sched_migration_cost = 500000UL; +/* +* The usage window over which average use is computed for shares +* distribution. +*/ +unsigned int __read_mostly sysctl_sched_shares_window =10000000UL ; +static const struct sched_class fair_sched_class;/**************************************************************
@@ -688,7 +694,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),
RFC 8/12 sched: update shares on idle_balance
In reply to [email protected]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.
--- 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 ;
RFC 9/12 sched: demand based update_cfs_load()
In reply to [email protected]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.
--- 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;
RFC 10/12 sched: allow update_cfs_load to update global load
In reply to [email protected]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_of (se), 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_of (se),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
RFC 11/12 sched: update tg->shares after cpu.shares write
In reply to [email protected]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.
--- 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:
RFC 12/12 debug: export effective shares for analysis versus specified
In reply to [email protected]--- kernel/sched.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)
sched.c renamed from sched.c.orig +19 -0
@@ -8607,6 +8607,21 @@ static u64 cpu_shares_read_u64(struct cg return (u64) tg->shares; } + +static u64 cpu_issued_shares_read_u64 (struct cgroup *cgrp,struct cftype *cft) +{ +struct task_group *tg =cgroup_tg (cgrp); +u64 result =0 ; +int i; + +if (!tg->se[0 ]) +return 0 ; + +for_each_online_cpu (i) + result += tg->se[i]->load.weight; + +return result; +}#endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_RT_GROUP_SCHED
@@ -8640,6 +8655,10 @@ static struct cftype cpu_files[] = { .read_u64 = cpu_shares_read_u64, .write_u64 = cpu_shares_write_u64, }, + { + .name = "issued_shares", + .read_u64 = cpu_issued_shares_read_u64, + },#endif #ifdef CONFIG_RT_GROUP_SCHED {
Quoted 15 lines · On Fri, 2010-10-15 at 21:43 -0700, [email protected] wrote:
Hi all,
Peter previously posted a patchset that attempted to improve the problem of
task_groupshare distribution. This is something that has been a long-time pain point for group scheduling. The existing algorithm considers distributions on a per-cpu-per-domain basis and carries a fairly high update overhead, especially on larger machines.I was previously looking at improving this using Fenwick trees to allow a single sum without the exorbitant cost but then Peter's idea above was better :).
The kernel is that by monitoring the average contribution to load on a per-cpu-per-taskgroup basis we can distribute the weight for which we are expected to consume.
Quoted 6 lines
This set extends the original posting with a focus on increased fairness and reduced convergence (to true average) time. In particular the case of large over-commit in the case of a distributed wake-up is a concern which is now fairly well addressed.
Obviously everything's experimental but it should be stable/fair.
I like what you've done with it, my only worry is 10/12 where you allow for extra updates to the global state -- I think they should be fairly limited in number, and I can see the need for the update if we get too far out of whack, but it is something to look at while testing this stuff.
Quoted 2 lines
TODO:
- Validate any RT interaction
I don't think there's anything to worry about there, the only interaction which there is between this and the rt scheduling classes is the initial sharing of the load-avg window, but you 'cure' that in 7/12.
(I think that sysctl wants a _us postfix someplace and we thus want some NSEC_PER_USEC multiplication in there).
Quoted 1 line
- Continue collecting/analyzing performance and fairness data
Yes please ;-), I'll try and run this on some machines as well.
Quoted 1 line
- Should the shares period just be the
sched_latency?
Interesting idea.. lets keep it a separate sysctl for now for easy tuning, if things settle down and we're still good in that range we can consider merging them.
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · On Fri, 2010-10-15 at 21:43 -0700, [email protected] wrote:
Hi all,
Peter previously posted a patchset that attempted to improve the problem of
task_groupshare distribution. This is something that has been a long-time pain point for group scheduling. The existing algorithm considers distributions on a per-cpu-per-domain basis and carries a fairly high update overhead, especially on larger machines.I was previously looking at improving this using Fenwick trees to allow a single sum without the exorbitant cost but then Peter's idea above was better :).
The kernel is that by monitoring the average contribution to load on a per-cpu-per-taskgroup basis we can distribute the weight for which we are expected to consume.
This set extends the original posting with a focus on increased fairness and reduced convergence (to true average) time. In particular the case of large over-commit in the case of a distributed wake-up is a concern which is now fairly well addressed.
Quoted 8 lines
Quoted 1 line
Obviously everything's experimental but it should be stable/fair.
I like what you've done with it, my only worry is 10/12 where you allow for extra updates to the global state -- I think they should be fairly limited in number, and I can see the need for the update if we get too far out of whack, but it is something to look at while testing this stuff.
So my original answer here was to only update when there was load and it was > n% delta which stops 1 thread waking up and sleeping from thrashing it, but the 2 thread case is just as obviously broken for any n. It needs a rate limit but I'm sort of loathe to introduce _another_ set of timestamps. I don't suppose there's much harm in doing so though and I don't think it's going to be clean to overload one of the existing ones so perhaps another counter is the answer.
I'll make sure this is addressed in v2.
Quoted 10 lines
Quoted 2 lines
TODO:
- Validate any RT interactionI don't think there's anything to worry about there, the only interaction which there is between this and the rt scheduling classes is the initial sharing of the load-avg window, but you 'cure' that in 7/12.
(I think that sysctl wants a
_uspostfix someplace and we thus want someNSEC_PER_USECmultiplication in there).
Yes -- updated, thanks.
Quoted 12 lines
Quoted 1 line
- Continue collecting/analyzing performance and fairness data
Yes please ;-), I'll try and run this on some machines as well.
Quoted 1 line
- Should the shares period just be the
sched_latency?Interesting idea.. lets keep it a separate sysctl for now for easy tuning, if things settle down and we're still good in that range we can consider merging them.
Quoted 39 lines · Paul Turner
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · On Fri, 2010-10-15 at 21:43 -0700, [email protected] wrote:
Hi all,
Peter previously posted a patchset that attempted to improve the problem of
task_groupshare distribution. This is something that has been a long-time pain point for group scheduling. The existing algorithm considers distributions on a per-cpu-per-domain basis and carries a fairly high update overhead, especially on larger machines.I was previously looking at improving this using Fenwick trees to allow a single sum without the exorbitant cost but then Peter's idea above was better :).
The kernel is that by monitoring the average contribution to load on a per-cpu-per-taskgroup basis we can distribute the weight for which we are expected to consume.
This set extends the original posting with a focus on increased fairness and reduced convergence (to true average) time. In particular the case of large over-commit in the case of a distributed wake-up is a concern which is now fairly well addressed.
Quoted 8 lines
Quoted 1 line
Obviously everything's experimental but it should be stable/fair.
I like what you've done with it, my only worry is 10/12 where you allow for extra updates to the global state -- I think they should be fairly limited in number, and I can see the need for the update if we get too far out of whack, but it is something to look at while testing this stuff.
So my original answer here was to only update when there was load and it was > n% delta which stops 1 thread waking up and sleeping from thrashing it, but the 2 thread case is just as obviously broken for any n. It needs a rate limit but I'm sort of loathe to introduce _another_ set of timestamps. I don't suppose there's much harm in doing so though and I don't think it's going to be clean to overload one of the existing ones so perhaps another counter is the answer.
Quoted 1 line
I'll make sure this is addressed in v2.
Ahh -- I remember my original reasoning here now:
These global updates are rate limited since they only occur when we fold the averaging period thus are limited to occur at a rate of period/2 (e.g. each time we fold).
One concern is we could get a local "storm" since several cgroups could trip this limit at the same time.. but it's also obviously not going to be any worse than an update_shares_cpu().
While there may be a concern on *giant* cpu systems, I think we already have that problem in both the original and (to a lesser extent) current approaches.
Quoted 27 lines
Quoted 11 lines
Quoted 3 lines
TODO:
- Validate any RT interactionI don't think there's anything to worry about there, the only interaction which there is between this and the rt scheduling classes is the initial sharing of the load-avg window, but you 'cure' that in 7/12.
(I think that sysctl wants a
_uspostfix someplace and we thus want someNSEC_PER_USECmultiplication in there).Yes -- updated, thanks.
Quoted 12 lines
Quoted 1 line
- Continue collecting/analyzing performance and fairness data
Yes please ;-), I'll try and run this on some machines as well.
Quoted 1 line
- Should the shares period just be the
sched_latency?Interesting idea.. lets keep it a separate sysctl for now for easy tuning, if things settle down and we're still good in that range we can consider merging them.
Quoted 29 lines · * [email protected] <[email protected]> [2010-10-15 21:43:49]:
Hi all,
Peter previously posted a patchset that attempted to improve the problem of
task_groupshare distribution. This is something that has been a long-time pain point for group scheduling. The existing algorithm considers distributions on a per-cpu-per-domain basis and carries a fairly high update overhead, especially on larger machines.I was previously looking at improving this using Fenwick trees to allow a single sum without the exorbitant cost but then Peter's idea above was better :).
The kernel is that by monitoring the average contribution to load on a per-cpu-per-taskgroup basis we can distribute the weight for which we are expected to consume.
This set extends the original posting with a focus on increased fairness and reduced convergence (to true average) time. In particular the case of large over-commit in the case of a distributed wake-up is a concern which is now fairly well addressed.
Obviously everything's experimental but it should be stable/fair.
Some motivation:
24 thread intel box, 150 active cgroups, multiple threads/group, load at ~90% (10 second sample):
tip:2.64% [k] tg_shares_up <!> 0.15% [k] __set_se_shares
Quoted 7 lines
patched:
0.02% [k] update_cfs_load 0.01% [k] update_cpu_load 0.00% [k] update_cfs_sharesSome fairness coverage for the above at: http://rs5.risingnet.net/~pjt/patches/shares_data_v1.txt
The results do sound interesting, could I recommend that you try to get 1000 cgroups or so, with half of them as active and half inactive. I'd also suggest tracking system and user time at the cgroup level.
Signature · 2 lines
Three Cheers, Balbir
Quoted 4 lines · Balbir Singh
The results do sound interesting, could I recommend that you try to get 1000 cgroups or so, with half of them as active and half inactive. I'd also suggest tracking system and user time at the cgroup level.
Sure, but do keep in mind that 500 active cgroups will always utterly suck no matter what you do, it means we do indeed need to iterate 500 cgroups for a lot of scheduler operations.
Quoted 10 lines · Peter Zijlstra
Quoted 4 lines · Balbir Singh
The results do sound interesting, could I recommend that you try to get 1000 cgroups or so, with half of them as active and half inactive. I'd also suggest tracking system and user time at the cgroup level.
Sure, but do keep in mind that 500 active cgroups will always utterly suck no matter what you do, it means we do indeed need to iterate 500 cgroups for a lot of scheduler operations.
I agree in general, but in my case I've seen nasty things even when the groups were empty.
Signature · 2 lines
Three Cheers, Balbir
Hi All
Here is a some performance data for the previously posted patches running a LAMP workload in a cloud-like environment which show promising reductions in CPU utilization. In this particular test, 32 groups equaling 64 KVM guests (each group consists of an Apache server guest and a MySQL server guest) are running a LAMP workload being driven by external load drivers. When using the default values in /etc/cgconfig.conf:
mount {
cpuset = /cgroup/cpuset;
cpu = /cgroup/cpu;
cpuacct = /cgroup/cpuacct;
memory = /cgroup/memory;
devices = /cgroup/devices;
freezer = /cgroup/freezer;
net_cls = /cgroup/net_cls;
blkio = /cgroup/blkio;
}which enable libvirt usage of cgroups the contents of /proc/cgroups looks like this before launching the guests:
#subsys_name hierarchy num_cgroups enabled cpuset 1 4 1 ns 0 1 1 cpu 2 4 1 cpuacct 3 4 1 memory 4 4 1 devices 5 4 1 freezer 6 4 1 net_cls 7 1 1 blkio 8 1 1
and like this after launching the guests:
#subsys_name hierarchy num_cgroups enabled cpuset 1 68 1 ns 0 1 1 cpu 2 68 1 cpuacct 3 68 1 memory 4 68 1 devices 5 68 1 freezer 6 68 1 net_cls 7 1 1 blkio 8 1 1
When running the workload the run with the patches used significantly less CPU:
Host CPU utilization with patches: 54.35%
Host CPU utilization without patches: 80.89%
Since the workload uses a fixed injection rate the achieved throughput for both test runs was the same, however the run with the patches applied did achieve better quality of service metrics.
NOTE: The runs were made using kvm.git changeset cec8b6b972a572b69d4902f57fb659e8a4c749af.
Signature · 1 line
Karl Rister <[email protected]>