sched,fair: flatten CPU controller runqueues
v2 cover sched,fair: flatten CPU controller runqueues
The current implementation of the CPU controller uses hierarchical runqueues, where on wakeup a task is enqueued on its group's runqueue, the group is enqueued on the runqueue of the group above it, etc.
This increases a fairly large amount of overhead for workloads that do a lot of wakeups a second, especially given that the default systemd hierarchy is 2 or 3 levels deep.
This patch series is an attempt at reducing that overhead, by placing all the tasks on the same runqueue, and scaling the task priority by the priority of the group, which is calculated periodically.
This patch series still has a number of TODO items:
- Clean up the code, and fix compilation without CONFIG_FAIR_GROUP_SCHED.
- Remove some more now unused code.
- Figure out a performance regression with our web server workload. I have fixed the schbench issue, now I need to find the less obvious stuff causing an increased number of involuntary preemptions...
- Reimplement CONFIG_CFS_BANDWIDTH.
Plan for the CONFIG_CFS_BANDWIDTH reimplementation:
- When a cgroup gets throttled, mark the cgroup and its children as throttled.
- When pick_next_entity finds a task that is on a throttled cgroup, stash it on the cgroup runqueue (which is not used for runnable tasks any more). Leave the vruntime unchanged, and adjust that runqueue's vruntime to be that of the left-most task.
- When a cgroup gets unthrottled, and has tasks on it, place it on a vruntime ordered heap separate from the main runqueue.
- Have pick_next_task_fair grab one task off that heap every time it is called, and the min vruntime of that heap is lower than the vruntime of the CPU's cfs_rq (or the CPU has no other runnable tasks).
- Place that selected task on the CPU's cfs_rq, renormalizing its vruntime with the GENTLE_FAIR_SLEEPERS logic. That should help interleave the already runnable tasks with the recently unthrottled group, and prevent thundering herd issues.
- If the group gets throttled again before all of its task had a chance to run, vruntime sorting ensures all the tasks in the throttled cgroup get a chance to run over time.
Changes from v1:
- use task_se_h_weight instead of task_se_h_load in calc_delta_fair and sched_slice, this seems to improve performance a little, but I still have some remaining regression to chase with our web server workload
- implement a number of the changes suggested by Dietmar Eggemann (still holding out for a better name for group_cfs_rq_of_parent)
This series applies on top of 5.2-rc6.
include/linux/sched.h | 6 kernel/sched/core.c | 2 kernel/sched/debug.c | 15 - kernel/sched/fair.c | 746 +++++++++++++++++++++----------------------------- kernel/sched/pelt.c | 53 +-- kernel/sched/pelt.h | 2 kernel/sched/sched.h | 10 7 files changed, 346 insertions(+), 488 deletions(-)
PATCH v2 1/10 sched: introduce task_se_h_load helper
Sometimes the hierarchical load of a sched_entity needs to be calculated. Rename task_h_load to task_se_h_load, and directly pass a sched_entity to that function.
Move the function declaration up above where it will be used later.
No functional changes.
--- kernel/sched/fair.c | 28 ++++++++++++++-------------- 1 file changed, 14 insertions(+), 14 deletions(-)
kernel/sched/fair.c +14 -14
@@ -242,6 +242,7 @@ static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weightconst struct sched_class fair_sched_class; +static unsigned long task_se_h_load (struct sched_entity *se);/************************************************************** * CFS operations on generic schedulable entities:
@@ -706,7 +707,6 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)#ifdef CONFIG_SMP static int select_idle_sibling (struct task_struct *p,int prev_cpu,int cpu); -static unsigned long task_h_load (struct task_struct *p);static unsigned long capacity_of (int cpu);/* Give new sched_entity start runnable values to heavy its load in infant time */
@@ -1668,7 +1668,7 @@ static void task_numa_compare(struct task_numa_env *env,/* * In the overloaded case, try and keep the load balanced. */ - load =task_h_load (env->p) -task_h_load (cur); + load =task_se_h_load (env->p->se) -task_se_h_load (cur->se);if (!load) goto assign;
@@ -1706,7 +1706,7 @@ static void task_numa_find_cpu(struct task_numa_env *env,bool maymove = false;int cpu; - load =task_h_load (env->p); + load =task_se_h_load (env->p->se); dst_load = env->dst_stats.load + load; src_load = env->src_stats.load - load;
@@ -3389,7 +3389,7 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum* avg. The immediate corollary is that all (fair) tasks must be attached, see * post_init_entity_util_avg(). * -* cfs_rq->avg is used for task_h_load() and update_cfs_share() for example. +* cfs_rq->avg is used for task_se_h_load() and update_cfs_share() for example. * * Returns true if the load decayed or we removed load. *
@@ -3522,7 +3522,7 @@ static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s/* * Track task load average for carrying it to new CPU after migrated, and -* track group sched_entity load average for task_h_load calc in migration +* track group sched_entity load average for task_se_h_load calc in migration */ if (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD ))__update_load_avg_se (now, cfs_rq, se);
@@ -3751,7 +3751,7 @@ static inline void update_misfit_status(struct task_struct *p, struct rq *rq) return; } - rq->misfit_task_load =task_h_load (p); + rq->misfit_task_load =task_se_h_load (&p->se); }#else /* CONFIG_SMP */
@@ -5739,7 +5739,7 @@ wake_affine_weight(struct sched_domain *sd, struct task_struct *p, this_eff_load =target_load (this_cpu, sd->wake_idx);if (sync) { -unsigned long current_load =task_h_load (current); +unsigned long current_load =task_se_h_load (¤t->se);if (current_load > this_eff_load)return this_cpu;
@@ -5747,7 +5747,7 @@ wake_affine_weight(struct sched_domain *sd, struct task_struct *p, this_eff_load -= current_load; } - task_load =task_h_load (p); + task_load =task_se_h_load (&p->se); this_eff_load += task_load;if (sched_feat (WA_BIAS ))
@@ -7600,7 +7600,7 @@ static int detach_tasks(struct lb_env *env)if (!can_migrate_task (p, env)) goto next; - load =task_h_load (p); + load =task_se_h_load (&p->se);if (sched_feat (LB_MIN ) && load <16 && !env->sd->nr_balance_failed) goto next;
@@ -7833,12 +7833,12 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } -static unsigned long task_h_load (struct task_struct *p) +static unsigned long task_se_h_load (struct sched_entity *se) { -struct cfs_rq *cfs_rq =task_cfs_rq (p); +struct cfs_rq *cfs_rq =cfs_rq_of (se);update_cfs_rq_h_load (cfs_rq); -return div64_ul (p->se.avg.load_avg * cfs_rq->h_load, +return div64_ul (se->avg.load_avg * cfs_rq->h_load,cfs_rq_load_avg (cfs_rq) +1 ); }#else
@@ -7865,9 +7865,9 @@ static inline void update_blocked_averages(int cpu) rq_unlock_irqrestore(rq, &rf); } -static unsigned long task_h_load (struct task_struct *p) +static unsigned long task_se_h_load (struct sched_entity *se) { -return p->se.avg.load_avg; +return se->avg.load_avg; }#endif
Signature · 1 line
2.20.1
Re: [PATCH 01/10] sched: introduce task_se_h_load helper
Quoted 9 lines · Rik van Riel
Sometimes the hierarchical load of a
sched_entityneeds to be calculated. Renametask_h_loadtotask_se_h_load, and directly pass asched_entityto that function.Move the function declaration up above where it will be used later.
No functional changes.
Signed-off-by Rik van Riel <[email protected]>
Thanks,
Josef
PATCH v2 2/10 sched: change /proc/sched_debug fields
In reply to Rik van RielRemove some fields from /proc/sched_debug that are removed from sched_entity in a subsequent patch, and add h_load, which comes in very handy to debug CPU controller weight distribution.
--- kernel/sched/debug.c | 11 ++--------- 1 file changed, 2 insertions(+), 9 deletions(-)
kernel/sched/debug.c +2 -9
@@ -416,11 +416,9 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group }P (se->load.weight); -P (se->runnable_weight);#ifdef CONFIG_SMP P (se->avg.load_avg);P (se->avg.util_avg); -P (se->avg.runnable_load_avg);#endif #undef PN_SCHEDSTAT
@@ -538,7 +536,6 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)SEQ_printf (m," .%-30s: %d\n" ,"nr_running" , cfs_rq->nr_running);SEQ_printf (m," .%-30s: %ld\n" ,"load" , cfs_rq->load.weight);#ifdef CONFIG_SMP -SEQ_printf (m," .%-30s: %ld\n" ,"runnable_weight" , cfs_rq->runnable_weight);SEQ_printf (m," .%-30s: %lu\n" ,"load_avg" , cfs_rq->avg.load_avg); SEQ_printf(m, " .%-30s: %lu\n", "runnable_load_avg",
@@ -547,17 +544,15 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) cfs_rq->avg.util_avg);SEQ_printf (m," .%-30s: %u\n" ,"util_est_enqueued" , cfs_rq->avg.util_est.enqueued); -SEQ_printf (m," .%-30s: %ld\n" ,"removed.load_avg" , - cfs_rq->removed.load_avg);SEQ_printf (m," .%-30s: %ld\n" ,"removed.util_avg" , cfs_rq->removed.util_avg); -SEQ_printf (m," .%-30s: %ld\n" ,"removed.runnable_sum" , - cfs_rq->removed.runnable_sum);#ifdef CONFIG_FAIR_GROUP_SCHED SEQ_printf (m," .%-30s: %lu\n" ,"tg_load_avg_contrib" , cfs_rq->tg_load_avg_contrib);SEQ_printf (m," .%-30s: %ld\n" ,"tg_load_avg" ,atomic_long_read (&cfs_rq->tg->load_avg)); +SEQ_printf (m," .%-30s: %lu\n" ,"h_load" , + cfs_rq->h_load);#endif #endif #ifdef CONFIG_CFS_BANDWIDTH
@@ -961,10 +956,8 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns, "nr_involuntary_switches", (long long)p->nivcsw);P (se.load.weight); -P (se.runnable_weight);#ifdef CONFIG_SMP P (se.avg.load_sum); -P (se.avg.runnable_load_sum);P (se.avg.util_sum);P (se.avg.load_avg);P (se.avg.runnable_load_avg);
Signature · 1 line
2.20.1
Re: [PATCH 02/10] sched: change /proc/sched_debug fields
Quoted 5 lines · Rik van Riel
Remove some fields from
/proc/sched_debugthat are removed fromsched_entityin a subsequent patch, and addh_load, which comes in very handy to debug CPU controller weight distribution.Signed-off-by Rik van Riel <[email protected]>
Thanks,
Josef
PATCH v2 3/10 sched,fair: redefine runnable_load_avg as the sum of task_h_load
In reply to Rik van RielThe runnable_load magic is used to quickly propagate information about runnable tasks up the hierarchy of runqueues. The runnable_load_avg is mostly used for the load balancing code, which only examines the value at the root cfs_rq.
Redefine the root cfs_rq runnable_load_avg to be the sum of task_h_loads of the runnable tasks. This works because the hierarchical runnable_load of a task is already equal to the task_se_h_load today. This provides enough information to the load balancer.
The runnable_load_avg of the cgroup cfs_rqs does not appear to be used for anything, so don't bother calculating those.
This removes one of the things that the code currently traverses the cgroup hierarchy for, and getting rid of it brings us one step closer to a flat runqueue for the CPU controller.
--- include/linux/sched.h | 3 +- kernel/sched/core.c | 2 - kernel/sched/debug.c | 1 + kernel/sched/fair.c | 125 +++++++++++++----------------------------- kernel/sched/pelt.c | 49 ++++++----------- kernel/sched/sched.h | 6 -- 6 files changed, 55 insertions(+), 131 deletions(-)
include/linux/sched.h +1 -2
@@ -391,7 +391,6 @@ struct util_est {struct sched_avg {u64 last_update_time;u64 load_sum; -u64 runnable_load_sum;u32 util_sum;u32 period_contrib;unsigned long load_avg;
@@ -439,7 +438,6 @@ struct sched_statistics {struct sched_entity {/* For load-balancing: */ struct load_weight load; -unsigned long runnable_weight;struct rb_node run_node;struct list_head group_node;unsigned int on_rq;
@@ -455,6 +453,7 @@ struct sched_entity {#ifdef CONFIG_FAIR_GROUP_SCHED int depth; +unsigned long enqueued_h_load;struct sched_entity *parent;/* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq;
kernel/sched/core.c +0 -2
@@ -744,7 +744,6 @@ static void set_load_weight(struct task_struct *p, bool update_load)if (task_has_idle_policy (p)) { load->weight =scale_load (WEIGHT_IDLEPRIO ); load->inv_weight =WMULT_IDLEPRIO ; - p->se.runnable_weight = load->weight;return ; }
@@ -757,7 +756,6 @@ static void set_load_weight(struct task_struct *p, bool update_load) }else { load->weight =scale_load (sched_prio_to_weight[prio]); load->inv_weight = sched_prio_to_wmult[prio]; - p->se.runnable_weight = load->weight; } }
kernel/sched/debug.c +1 -0
@@ -962,6 +962,7 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,P (se.avg.load_avg);P (se.avg.runnable_load_avg);P (se.avg.util_avg); +P (se.enqueued_h_load);P (se.avg.last_update_time);P (se.avg.util_est.ewma);P (se.avg.util_est.enqueued);
kernel/sched/fair.c +37 -88
235 lines not on this page · raw message
kernel/sched/pelt.c +16 -33
164 lines not on this page · raw message
kernel/sched/sched.h +0 -6
@@ -487,7 +487,6 @@ struct cfs_bandwidth { };/* CFS-related fields in a runqueue */ struct cfs_rq {struct load_weight load; -unsigned long runnable_weight;unsigned int nr_running;unsigned int h_nr_running;
@@ -700,11 +699,6 @@ static inline long se_weight(struct sched_entity *se)return scale_load_down (se->load.weight); } -static inline long se_runnable (struct sched_entity *se) -{ -return scale_load_down (se->runnable_weight); -} -static inline bool sched_asym_prefer (int a,int b) {return arch_asym_cpu_priority (a) >arch_asym_cpu_priority (b);
Signature · 1 line
2.20.1
Re: [PATCH 03/10] sched,fair: redefine runnable_load_avg as the sum of task_h_load
Quoted 10 lines · Rik van Riel
The
runnable_loadmagic is used to quickly propagate information about runnable tasks up the hierarchy of runqueues. Therunnable_load_avgis mostly used for the load balancing code, which only examines the value at the rootcfs_rq.Redefine the root
cfs_rqrunnable_load_avgto be the sum oftask_h_loadsof the runnable tasks. This works because the hierarchicalrunnable_loadof a task is already equal to thetask_se_h_loadtoday. This provides enough information to the load balancer.
Quoted 7 lines
The
runnable_load_avgof the cgroupcfs_rqsdoes not appear to be used for anything, so don't bother calculating those.This removes one of the things that the code currently traverses the cgroup hierarchy for, and getting rid of it brings us one step closer to a flat runqueue for the CPU controller.
My memory on this stuff is very hazy, but IIRC we had the runnable_sum and the runnable_avg separated out because you could have the avg lag behind the sum. So like you enqueue a bunch of new entities who's avg may have decayed a bunch and so their overall load is not felt on the CPU until they start running, and now you've overloaded that CPU. The sum was there to make sure new things coming onto the CPU added actual load to the queue instead of looking like there was no load.
Is this going to be a problem now with this new code?
<snip>
Quoted 7 lines
kernel/sched/fair.c +7
-0+static inline void +update_runnable_load_avg (struct sched_entity *se) +{ +struct cfs_rq *root_cfs_rq = &cfs_rq_of (se)->rq->cfs; +long new_h_load, delta; + +SCHED_WARN_ON (!entity_is_task (se));
kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 2798
Quoted 10 lines
kernel/sched/fair.c +6
-3+ +if (!se->on_rq) +return ; -sub_positive (&cfs_rq->avg.runnable_load_avg, se->avg.runnable_load_avg); -sub_positive (&cfs_rq->avg.runnable_load_sum, -se_runnable (se) * se->avg.runnable_load_sum); + new_h_load =task_se_h_load (se); + delta = new_h_load - se->enqueued_h_load; + root_cfs_rq->avg.runnable_load_avg += delta;
Should we use add_positive here? Thanks,
Josef
Re: [PATCH 03/10] sched,fair: redefine runnable_load_avg as the sum of task_h_load
Quoted 41 lines · Josef Bacik
Quoted 16 lines · Rik van Riel
The
runnable_loadmagic is used to quickly propagate information about
runnable tasks up the hierarchy of runqueues. Therunnable_load_avgis
mostly used for the load balancing code, which only examines the value at
the rootcfs_rq.Redefine the root
cfs_rqrunnable_load_avgto be the sum oftask_h_loads
of the runnable tasks. This works because the hierarchicalrunnable_loadof
a task is already equal to thetask_se_h_loadtoday. This provides enough
information to the load balancer.Quoted 9 lines
The
runnable_load_avgof the cgroupcfs_rqsdoes not appear to be used for anything, so don't bother calculating those.This removes one of the things that the code currently traverses the
cgroup hierarchy for, and getting rid of it brings us one step closer
to a flat runqueue for the CPU controller.My memory on this stuff is very hazy, but IIRC we had the
runnable_sumand therunnable_avgseparated out because you could have the avg lag behind the sum.
So like you enqueue a bunch of new entities who's avg may have decayed a bunch
and so their overall load is not felt on the CPU until they start running, and
now you've overloaded that CPU. The sum was there to make sure new things
coming onto the CPU added actual load to the queue instead of looking like there
was no load.
Quoted 1 line
Is this going to be a problem now with this new code?
That is a good question!
On the one hand, you may well be right.
On the other hand, while I see the old code calculating runnable_sum, I don't really see it _using_ it to drive scheduling decisions.
It would be easy to define the CPU cfs_rq->runnable_load_sum as being the sum of task_se_h_weight() of each runnable task on the CPU (for example), but what would we use it for?
What am I missing?
Quoted 12 lines
+static inline void
Quoted 11 lines
kernel/sched/fair.c +9
-1+update_runnable_load_avg(struct sched_entity *se) +{ +struct cfs_rq *root_cfs_rq = &cfs_rq_of (se)->rq->cfs; +long new_h_load, delta; + +SCHED_WARN_ON (!entity_is_task (se)); + +if (!se->on_rq) +return ; - sub_positive(&cfs_rq->avg.runnable_load_avg, se-
Quoted 8 lines
kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 2798
Quoted 6 lines
Quoted 1 line
avg.runnable_load_avg);
kernel/sched/fair.c +3
-2-sub_positive (&cfs_rq->avg.runnable_load_sum, -se_runnable (se) * se->avg.runnable_load_sum); + new_h_load =task_se_h_load (se); + delta = new_h_load - se->enqueued_h_load; + root_cfs_rq->avg.runnable_load_avg += delta;Should we use
add_positivehere? Thanks,
Yes, we should use add_positive. I'll do that for v3.
Signature · 1 line
All Rights Reversed.
Re: [PATCH 03/10] sched,fair: redefine runnable_load_avg as the sum of task_h_load
Quoted 52 lines · Rik van Riel
Quoted 41 lines · Josef Bacik
Quoted 16 lines · Rik van Riel
The
runnable_loadmagic is used to quickly propagate information about
runnable tasks up the hierarchy of runqueues. Therunnable_load_avgis
mostly used for the load balancing code, which only examines the value at
the rootcfs_rq.Redefine the root
cfs_rqrunnable_load_avgto be the sum oftask_h_loads
of the runnable tasks. This works because the hierarchicalrunnable_loadof
a task is already equal to thetask_se_h_loadtoday. This provides enough
information to the load balancer.Quoted 9 lines
The
runnable_load_avgof the cgroupcfs_rqsdoes not appear to be used for anything, so don't bother calculating those.This removes one of the things that the code currently traverses the
cgroup hierarchy for, and getting rid of it brings us one step closer
to a flat runqueue for the CPU controller.My memory on this stuff is very hazy, but IIRC we had the
runnable_sumand therunnable_avgseparated out because you could have the avg lag behind the sum.
So like you enqueue a bunch of new entities who's avg may have decayed a bunch
and so their overall load is not felt on the CPU until they start running, and
now you've overloaded that CPU. The sum was there to make sure new things
coming onto the CPU added actual load to the queue instead of looking like there
was no load.Quoted 1 line
Is this going to be a problem now with this new code?
That is a good question!
On the one hand, you may well be right.
On the other hand, while I see the old code calculating
runnable_sum, I don't really see it _using_ it to drive scheduling decisions.
Quoted 5 lines
It would be easy to define the CPU
cfs_rq->runnable_load_sumas being the sum oftask_se_h_weight()of each runnable task on the CPU (for example), but what would we use it for?What am I missing?
It's suuuuuper sublte, but you're right in that we don't really need the runnable_avg per-se, but what you do is you kill calc_group_runnable, which used to do this
load_avg = max(cfs_rq->avg.load_avg,
scale_load_down(cfs_rq->load.weight));
runnable = max(cfs_rq->avg.runnable_load_avg,
scale_load_down(cfs_rq->runnable_weight));
so we'd account for this weirdness of adding a previously idle process to a new CPU and overloading the CPU because we'd add a bunch of these 0 weight looking tasks that suddenly all wake up and are on the same CPU. So we used the runnable_weight to account for what was actually happening, and the max of load_avg and the weight to figure out what the potential load would be.
What you've done here is change the weighting stuff to be completely based on load avg, which is problematic for the reasons above. Did you fix this later on in your patches? If so then just tell me to keep reading and I'll do that ;). Thanks,
Josef
Re: [PATCH 03/10] sched,fair: redefine runnable_load_avg as the sum of task_h_load
Quoted 59 lines · Josef Bacik
Quoted 29 lines · Rik van Riel
Quoted 18 lines · Josef Bacik
My memory on this stuff is very hazy, but IIRC we had the
runnable_sumand therunnable_avgseparated out because you could have the avg lag behind
the sum.
So like you enqueue a bunch of new entities who's avg may have decayed a bunch
and so their overall load is not felt on the CPU until they start running, and
now you've overloaded that CPU. The sum was there to make sure new
things
coming onto the CPU added actual load to the queue instead of looking
like there
was no load.Quoted 1 line
Is this going to be a problem now with this new code?
That is a good question!
On the one hand, you may well be right.
On the other hand, while I see the old code calculating
runnable_sum, I don't really see it _using_ it to drive scheduling decisions.Quoted 5 lines
It would be easy to define the CPU
cfs_rq->runnable_load_sumas being the sum oftask_se_h_weight()of each runnable task on the CPU (for example), but what would we use it for?What am I missing?
It's suuuuuper sublte, but you're right in that we don't really need the
runnable_avgper-se, but what you do is you killcalc_group_runnable, which used
to do this
load_avg= max(cfs_rq->avg.load_avg,scale_load_down(cfs_rq->load.weight));runnable = max(cfs_rq->avg.runnable_load_avg,
scale_load_down(cfs_rq->runnable_weight));so we'd account for this weirdness of adding a previously idle process to a new
CPU and overloading the CPU because we'd add a bunch of these 0 weight looking
tasks that suddenly all wake up and are on the same CPU. So we used therunnable_weightto account for what was actually happening, and the max ofload_avgand the weight to figure out what the potential load would be.
Quoted 6 lines
What you've done here is change the weighting stuff to be completely based on
load avg, which is problematic for the reasons above. Did you fix this later on
in your patches? If so then just tell me to keep reading and I'll do that ;).
No, I have not fixed that later in the code.
I am not entirely sure how I could do that, without reintroducing walking the hierarchy at task enqueue and dequeue, but maybe you have some idea...
Signature · 1 line
All Rights Reversed.
PATCH v2 4/10 sched,fair: move runnable_load_avg to cfs_rq
In reply to Rik van RielSince only the root cfs_rq runnable_load_avg field is used any more, we can move the field from struct sched_avg, which every sched_entity has one of, directly into the struct cfs_rq, of which we have way fewer.
No functional changes.
--- include/linux/sched.h | 1 - kernel/sched/debug.c | 3 +-- kernel/sched/fair.c | 8 ++++---- kernel/sched/sched.h | 1 + 4 files changed, 6 insertions(+), 7 deletions(-)
include/linux/sched.h +0 -1
@@ -394,7 +394,6 @@ struct sched_avg {u32 util_sum;u32 period_contrib;unsigned long load_avg; -unsigned long runnable_load_avg;unsigned long util_avg;struct util_est util_est; }____cacheline_aligned ;
kernel/sched/debug.c +1 -2
@@ -539,7 +539,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)SEQ_printf (m," .%-30s: %lu\n" ,"load_avg" , cfs_rq->avg.load_avg);SEQ_printf (m," .%-30s: %lu\n" ,"runnable_load_avg" , - cfs_rq->avg.runnable_load_avg); + cfs_rq->runnable_load_avg);SEQ_printf (m," .%-30s: %lu\n" ,"util_avg" , cfs_rq->avg.util_avg); SEQ_printf(m, " .%-30s: %u\n", "util_est_enqueued",
@@ -960,7 +960,6 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,P (se.avg.load_sum);P (se.avg.util_sum);P (se.avg.load_avg); -P (se.avg.runnable_load_avg);P (se.avg.util_avg);P (se.enqueued_h_load);P (se.avg.last_update_time);
kernel/sched/fair.c +4 -4
@@ -2768,7 +2768,7 @@ enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)struct cfs_rq *root_cfs_rq = &cfs_rq->rq->cfs; se->enqueued_h_load =task_se_h_load (se); - root_cfs_rq->avg.runnable_load_avg += se->enqueued_h_load; + root_cfs_rq->runnable_load_avg += se->enqueued_h_load; } }
@@ -2777,7 +2777,7 @@ dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {if (entity_is_task (se)) {struct cfs_rq *root_cfs_rq = &cfs_rq->rq->cfs; -sub_positive (&root_cfs_rq->avg.runnable_load_avg, +sub_positive (&root_cfs_rq->runnable_load_avg, se->enqueued_h_load); } }
@@ -2795,7 +2795,7 @@ update_runnable_load_avg(struct sched_entity *se) new_h_load =task_se_h_load (se); delta = new_h_load - se->enqueued_h_load; - root_cfs_rq->avg.runnable_load_avg += delta; + root_cfs_rq->runnable_load_avg += delta; se->enqueued_h_load = new_h_load; }
@@ -3559,7 +3559,7 @@ static void remove_entity_load_avg(struct sched_entity *se)static inline unsigned long cfs_rq_runnable_load_avg (struct cfs_rq *cfs_rq) { -return cfs_rq->avg.runnable_load_avg; +return cfs_rq->runnable_load_avg; }static inline unsigned long cfs_rq_load_avg (struct cfs_rq *cfs_rq)
kernel/sched/sched.h +1 -0
@@ -516,6 +516,7 @@ struct cfs_rq {* CFS load tracking */ struct sched_avg avg; +unsigned long runnable_load_avg;#ifndef CONFIG_64BIT u64 load_last_update_time_copy;#endif
Signature · 1 line
2.20.1
PATCH v2 5/10 sched,fair: remove cfs rqs from leaf_cfs_rq_list bottom up
In reply to Rik van RielReducing the overhead of the CPU controller is achieved by not walking all the sched_entities every time a task is enqueued or dequeued.
One of the things being checked every single time is whether the cfs_rq is on the rq->leaf_cfs_rq_list.
By only removing a cfs_rq from the list once it no longer has children on the list, we can avoid walking the sched_entity hierarchy if the bottom cfs_rq is on the list, once the runqueues have been flattened.
--- kernel/sched/fair.c | 17 +++++++++++++++++ kernel/sched/sched.h | 1 + 2 files changed, 18 insertions(+)
kernel/sched/fair.c +17 -0
@@ -286,6 +286,13 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) cfs_rq->on_list =1 ; +/* +* If the tmp_alone_branch cursor was moved, it means a child cfs_rq +* is already on the list ahead of us. +*/ +if (rq->tmp_alone_branch != &rq->leaf_cfs_rq_list) + cfs_rq->children_on_list++; +/* * Ensure we either appear before our parent (if already * enqueued) or force our parent to appear after us when it is
@@ -311,6 +318,7 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)* list. */ rq->tmp_alone_branch = &rq->leaf_cfs_rq_list; + cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list++;return true; }
@@ -359,6 +367,11 @@ static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)if (rq->tmp_alone_branch == &cfs_rq->leaf_cfs_rq_list) rq->tmp_alone_branch = cfs_rq->leaf_cfs_rq_list.prev; +if (cfs_rq->tg->parent) { +int cpu =cpu_of (rq); + cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list--; + } +list_del_rcu (&cfs_rq->leaf_cfs_rq_list); cfs_rq->on_list =0 ; }
@@ -7687,6 +7700,10 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)if (cfs_rq->avg.util_sum)return false; +/* Remove decayed parents once their decayed children are gone. */ +if (cfs_rq->children_on_list) +return false; +return true; }
kernel/sched/sched.h +1 -0
@@ -557,6 +557,7 @@ struct cfs_rq {* This list is used during load balance. */ int on_list; +int children_on_list;struct list_head leaf_cfs_rq_list;struct task_group *tg;/* group that "owns" this runqueue */
Signature · 1 line
2.20.1
Vincent Guittot
maintainerRe: [PATCH 05/10] sched,fair: remove cfs rqs from leaf_cfs_rq_list bottom up
Quoted 56 lines · Rik van Riel
Reducing the overhead of the CPU controller is achieved by not walking all the
sched_entitiesevery time a task is enqueued or dequeued.One of the things being checked every single time is whether the
cfs_rqis on therq->leaf_cfs_rq_list.By only removing a
cfs_rqfrom the list once it no longer has children on the list, we can avoid walking thesched_entityhierarchy if the bottomcfs_rqis on the list, once the runqueues have been flattened.Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 +++++++++++++++++ kernel/sched/sched.h | 1 + 2 files changed, 18 insertions(+)kernel/sched/fair.c +13
-0@@ -286,6 +286,13 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) cfs_rq->on_list =1 ; +/* +* If the tmp_alone_branch cursor was moved, it means a child cfs_rq +* is already on the list ahead of us. +*/ +if (rq->tmp_alone_branch != &rq->leaf_cfs_rq_list) + cfs_rq->children_on_list++; +/* * Ensure we either appear before our parent (if already * enqueued) or force our parent to appear after us when it is @@ -311,6 +318,7 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)* list. */ rq->tmp_alone_branch = &rq->leaf_cfs_rq_list; + cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list++;return true; }@@ -359,6 +367,11 @@ static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)if (rq->tmp_alone_branch == &cfs_rq->leaf_cfs_rq_list) rq->tmp_alone_branch = cfs_rq->leaf_cfs_rq_list.prev; +if (cfs_rq->tg->parent) { +int cpu =cpu_of (rq); + cfs_rq->tg->parent->cfs_rq[cpu]->children_on_list--; + } +list_del_rcu (&cfs_rq->leaf_cfs_rq_list); cfs_rq->on_list =0 ; }
kernel/sched/fair.c static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq) · line 7704
Quoted 5 lines
kernel/sched/fair.c +2
-0@@ -7687,6 +7700,10 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)if (cfs_rq->avg.util_sum)return false; +/* Remove decayed parents once their decayed children are gone. */ +if (cfs_rq->children_on_list)
I'm not sure that you really need to count whether childrens are on the list. Instead you can take advantage of the list ordering and you only have to test if the previous cfs_rq in the list is a child. If it's not then there is no more child
and you can remove the new field children_on_list and inc/dec it
Quoted 20 lines
kernel/sched/fair.c +2
-0+return false; +return true; }kernel/sched/sched.h +1
-1@@ -557,6 +557,7 @@ struct cfs_rq {* This list is used during load balance. */ int on_list; +int children_on_list;struct list_head leaf_cfs_rq_list;struct task_group *tg;/* group that "owns" this runqueue */ --2.20.1
Re: [PATCH 05/10] sched,fair: remove cfs rqs from leaf_cfs_rq_list bottom up
Quoted 20 lines · Vincent Guittot
Quoted 10 lines · Rik van Riel
Reducing the overhead of the CPU controller is achieved by not walking
all thesched_entitiesevery time a task is enqueued or dequeued.kernel/sched/fair.c +1
-0@@ -7687,6 +7700,10 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)if (cfs_rq->avg.util_sum)return false; +/* Remove decayed parents once their decayed children are Quoted 2 lines
gone. */
+ if (cfs_rq->children_on_list)I'm not sure that you really need to count whether childrens are on the list.
Instead you can take advantage of the list ordering and you only have to test if the previouscfs_rqin the list is a child. If it's not then there is no more child
Quoted 1 line
and you can remove the new field
children_on_listand inc/dec it
Good suggestion. I'll do that for v3.
Thank you.
Signature · 1 line
All Rights Reversed.
PATCH v2 6/10 sched,cfs: use explicit cfs_rq of parent se helper
In reply to Rik van RielUse an explicit "cfs_rq of parent sched_entity" helper in a few strategic places, where cfs_rq_of(se) may no longer point at the right runqueue once we flatten the hierarchical cgroup runqueues.
No functional change.
--- kernel/sched/fair.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-)
kernel/sched/fair.c +13 -4
@@ -276,6 +276,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q; } +/* runqueue owned by the parent entity; the root cfs_rq for a top level se */ +static inline struct cfs_rq *group_cfs_rq_of_parent (struct sched_entity *se) +{ +if (se->parent) +return group_cfs_rq (se->parent); + +return cfs_rq_of (se); +} +static inline bool list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq) {struct rq *rq =rq_of (cfs_rq);
@@ -3297,7 +3306,7 @@ static inline int propagate_entity_load_avg(struct sched_entity *se) gcfs_rq->propagate =0 ; - cfs_rq =cfs_rq_of (se); + cfs_rq =group_cfs_rq_of_parent (se);add_tg_cfs_propagate (cfs_rq, gcfs_rq->prop_runnable_sum);
@@ -7778,7 +7787,7 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)WRITE_ONCE (cfs_rq->h_load_next,NULL );for_each_sched_entity (se) { - cfs_rq =cfs_rq_of (se); + cfs_rq =group_cfs_rq_of_parent (se);WRITE_ONCE (cfs_rq->h_load_next, se);if (cfs_rq->last_h_load_update == now)break ;
@@ -7801,7 +7810,7 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)static unsigned long task_se_h_load (struct sched_entity *se) { -struct cfs_rq *cfs_rq =cfs_rq_of (se); +struct cfs_rq *cfs_rq =group_cfs_rq_of_parent (se);update_cfs_rq_h_load (cfs_rq); return div64_ul(se->avg.load_avg * cfs_rq->h_load,
@@ -10148,7 +10157,7 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)struct sched_entity *se = &curr->se;for_each_sched_entity (se) { - cfs_rq =cfs_rq_of (se); + cfs_rq =group_cfs_rq_of_parent (se);entity_tick (cfs_rq, se, queued); }
Signature · 1 line
2.20.1
PATCH v2 7/10 sched,cfs: fix zero length timeslice calculation
In reply to Rik van RielThe way the time slice length is currently calculated, not only do high priority tasks get longer time slices than low priority tasks, but due to fixed point math, low priority tasks could end up with a zero length time slice. This can lead to cache thrashing and other inefficiencies.
Simplify the logic a little bit, and cap the minimum time slice length to sysctl_sched_min_granularity.
Tasks that end up getting a time slice length too long for their relative priority will simply end up having their vruntime advanced much faster than other tasks, resulting in them receiving time slices less frequently.
--- kernel/sched/fair.c | 25 ++++++++----------------- 1 file changed, 8 insertions(+), 17 deletions(-)
kernel/sched/fair.c +8 -17
@@ -671,22 +671,6 @@ static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)return delta; } -/* -* The idea is to set a period in which each task runs once. -* -* When there are too many tasks (sched_nr_latency) we have to stretch -* this period because otherwise the slices get too small. -* -* p = (nr <= nl) ? l : l*nr/nl -*/ -static u64 __sched_period (unsigned long nr_running) -{ -if (unlikely (nr_running > sched_nr_latency)) -return nr_running * sysctl_sched_min_granularity; -else -return sysctl_sched_latency; -} -/* * We calculate the wall-time slice from the period by taking a part * proportional to the weight.
@@ -695,7 +679,7 @@ static u64 __sched_period(unsigned long nr_running)*/ static u64 sched_slice (struct cfs_rq *cfs_rq,struct sched_entity *se) { -u64 slice =__sched_period (cfs_rq->nr_running + !se->on_rq); +u64 slice = sysctl_sched_latency;for_each_sched_entity (se) {struct load_weight *load;
@@ -712,6 +696,13 @@ static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) } slice =__calc_delta (slice, se->load.weight, load); } + +/* +* To avoid cache thrashing, run at least sysctl_sched_min_granularity. +* The vruntime of a low priority task advances faster; those tasks +* will simply get time slices less frequently. +*/ + slice =max_t (u64, slice, sysctl_sched_min_granularity);return slice; }
Signature · 1 line
2.20.1
Vincent Guittot
maintainerRe: [PATCH 07/10] sched,cfs: fix zero length timeslice calculation
Quoted 46 lines · Rik van Riel
The way the time slice length is currently calculated, not only do high priority tasks get longer time slices than low priority tasks, but due to fixed point math, low priority tasks could end up with a zero length time slice. This can lead to cache thrashing and other inefficiencies.
Simplify the logic a little bit, and cap the minimum time slice length to
sysctl_sched_min_granularity.Tasks that end up getting a time slice length too long for their relative priority will simply end up having their vruntime advanced much faster than other tasks, resulting in them receiving time slices less frequently.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 25 ++++++++----------------- 1 file changed, 8 insertions(+), 17 deletions(-)kernel/sched/fair.c +0
-16@@ -671,22 +671,6 @@ static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)return delta; } -/* -* The idea is to set a period in which each task runs once. -* -* When there are too many tasks (sched_nr_latency) we have to stretch -* this period because otherwise the slices get too small. -* -* p = (nr <= nl) ? l : l*nr/nl -*/ -static u64 __sched_period (unsigned long nr_running) -{ -if (unlikely (nr_running > sched_nr_latency)) -return nr_running * sysctl_sched_min_granularity; -else -return sysctl_sched_latency; -} -/* * We calculate the wall-time slice from the period by taking a part * proportional to the weight.
kernel/sched/fair.c static u64 __sched_period(unsigned long nr_running) · line 682
Quoted 5 lines
kernel/sched/fair.c +1
-1@@ -695,7 +679,7 @@ static u64 __sched_period(unsigned long nr_running)*/ static u64 sched_slice (struct cfs_rq *cfs_rq,struct sched_entity *se) { -u64 slice =__sched_period (cfs_rq->nr_running + !se->on_rq); +u64 slice = sysctl_sched_latency;
Is the change above and the remove of __sched_period() really needed for fixing the null time slice problem ?
This change impacts how tasks will preempt each other and as a result the throughput. It should have it dedicated patch so we can evaluate its impact
Quoted 20 lines
kernel/sched/fair.c +7
-1for_each_sched_entity (se) {struct load_weight *load;@@ -712,6 +696,13 @@ static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) } slice =__calc_delta (slice, se->load.weight, load); } + +/* +* To avoid cache thrashing, run at least sysctl_sched_min_granularity. +* The vruntime of a low priority task advances faster; those tasks +* will simply get time slices less frequently. +*/ + slice =max_t (u64, slice, sysctl_sched_min_granularity);return slice; } --2.20.1
Re: [PATCH 07/10] sched,cfs: fix zero length timeslice calculation
Quoted 63 lines · Vincent Guittot
Quoted 62 lines · Rik van Riel
The way the time slice length is currently calculated, not only do high
priority tasks get longer time slices than low priority tasks, but due
to fixed point math, low priority tasks could end up with a zero length
time slice. This can lead to cache thrashing and other inefficiencies.Simplify the logic a little bit, and cap the minimum time slice length
tosysctl_sched_min_granularity.Tasks that end up getting a time slice length too long for their relative
priority will simply end up having their vruntime advanced much faster than
other tasks, resulting in them receiving time slices less frequently.Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 25 ++++++++----------------- 1 file changed, 8 insertions(+), 17 deletions(-)kernel/sched/fair.c +0
-4@@ -671,22 +671,6 @@ static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)return delta; } -/* -* The idea is to set a period in which each task runs once. -* -* When there are too many tasks (sched_nr_latency) we have to stretch
- * this period because otherwise the slices get too small.
- *
- * p = (nr <= nl) ? l : l*nr/nl
- */kernel/sched/fair.c +0
-8-static u64 __sched_period (unsigned long nr_running) -{ -if (unlikely (nr_running > sched_nr_latency)) -return nr_running * sysctl_sched_min_granularity; -else -return sysctl_sched_latency; -} -/* * We calculate the wall-time slice from the period by taking a part
* proportional to the weight.kernel/sched/fair.c +0
-1@@ -695,7 +679,7 @@ static u64 __sched_period(unsigned longnr_running) */ static u64 sched_slice (struct cfs_rq *cfs_rq,struct sched_entity *se) { - u64 slice = __sched_period(cfs_rq->nr_running + !se-
Quoted 8 lines
kernel/sched/fair.c static u64 __sched_period(unsigned long · line 685
Quoted 2 lines
kernel/sched/fair.c +1
-0>on_rq); +u64 slice = sysctl_sched_latency;Is the change above and the remove of
__sched_period()really needed for fixing the null time slice problem ?
This change impacts how tasks will preempt each other and as a result the throughput. It should have it dedicated patch so we can evaluate its impact
Good point. I will split this up into two patches for v3.
Thank you.
Signature · 1 line
All Rights Reversed.
PATCH v2 8/10 sched,fair: refactor enqueue/dequeue_entity
In reply to Rik van RielRefactor enqueue_entity, dequeue_entity, and update_load_avg, in order to split out the things we still want to happen at every level in the cgroup hierarchy with a flat runqueue from the things we only need to happen once.
No functional changes.
--- kernel/sched/fair.c | 64 +++++++++++++++++++++++++++++---------------- 1 file changed, 42 insertions(+), 22 deletions(-)
kernel/sched/fair.c +42 -22
@@ -3480,7 +3480,7 @@ static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s#define DO_ATTACH 0x4/* Update task and its cfs_rq load average */ -static inline void update_load_avg (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) +static inline bool update_load_avg (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) {u64 now =cfs_rq_clock_pelt (cfs_rq);int decayed;
@@ -3509,6 +3509,8 @@ static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s }else if (decayed && (flags &UPDATE_TG ))update_tg_load_avg (cfs_rq,0 ); + +return decayed; }#ifndef CONFIG_64BIT
@@ -3725,9 +3727,10 @@ static inline void update_misfit_status(struct task_struct *p, struct rq *rq)#define SKIP_AGE_LOAD 0x0#define DO_ATTACH 0x0 -static inline void update_load_avg (struct cfs_rq *cfs_rq,struct sched_entity *se,int not_used1) +static inline bool update_load_avg (struct cfs_rq *cfs_rq,struct sched_entity *se,int not_used1) {cfs_rq_util_change (cfs_rq,0 ); +return false; }static inline void remove_entity_load_avg (struct sched_entity *se) {}
@@ -3850,6 +3853,24 @@ static inline void check_schedstat_required(void)* CPU and an up-to-date min_vruntime on the destination CPU. */ +static bool +enqueue_entity_groups (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) +{ +/* +* When enqueuing a sched_entity, we must: +* - Update loads to have both entity and cfs_rq synced with now. +* - Add its load to cfs_rq->runnable_avg +* - For group_entity, update its weight to reflect the new share of +* its group cfs_rq +* - Add its new weight to cfs_rq->load.weight +*/ +if (!update_load_avg (cfs_rq, se,UPDATE_TG |DO_ATTACH )) +return false; + +update_cfs_group (se); +return true; +} +static void enqueue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) {
@@ -3874,16 +3895,6 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (renorm && !curr) se->vruntime += cfs_rq->min_vruntime; -/* -* When enqueuing a sched_entity, we must: -* - Update loads to have both entity and cfs_rq synced with now. -* - Add its load to cfs_rq->runnable_avg -* - For group_entity, update its weight to reflect the new share of -* its group cfs_rq -* - Add its new weight to cfs_rq->load.weight -*/ -update_load_avg (cfs_rq, se,UPDATE_TG |DO_ATTACH ); -update_cfs_group (se);enqueue_runnable_load_avg (cfs_rq, se);account_entity_enqueue (cfs_rq, se);
@@ -3950,14 +3961,9 @@ static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se) static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq); -static void -dequeue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) +static bool +dequeue_entity_groups (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) { -/* -* Update run-time statistics of the 'current'. -*/ -update_curr (cfs_rq); -/* * When dequeuing a sched_entity, we must: * - Update loads to have both entity and cfs_rq synced with now.
@@ -3966,7 +3972,21 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)* - For group entity, update its weight to reflect the new share * of its group cfs_rq. */ -update_load_avg (cfs_rq, se,UPDATE_TG ); +if (!update_load_avg (cfs_rq, se,UPDATE_TG )) +return false; +update_cfs_group (se); + +return true; +} + +static void +dequeue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags) +{ +/* +* Update run-time statistics of the 'current'. +*/ +update_curr (cfs_rq); +dequeue_runnable_load_avg (cfs_rq, se);update_stats_dequeue (cfs_rq, se, flags);
@@ -3990,8 +4010,6 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)/* return excess runtime on last dequeue */ return_cfs_rq_runtime (cfs_rq); -update_cfs_group (se); -/* * Now advance min_vruntime if @se was the entity holding it back, * except when: DEQUEUE_SAVE && !DEQUEUE_MOVE, in this case we'll be
@@ -5156,6 +5174,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)if (se->on_rq)break ; cfs_rq =cfs_rq_of (se); +enqueue_entity_groups (cfs_rq, se, flags);enqueue_entity (cfs_rq, se, flags);/*
@@ -5238,6 +5257,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)for_each_sched_entity (se) { cfs_rq =cfs_rq_of (se); +dequeue_entity_groups (cfs_rq, se, flags);dequeue_entity (cfs_rq, se, flags);/*
Signature · 1 line
2.20.1
PATCH v2 9/10 sched,fair: add helper functions for flattened runqueue
In reply to Rik van RielAdd helper functions to make the flattened runqueue patch a little smaller.
The task_se_h_weight function is similar to task_se_h_load, but scales the task weight by the group weight, without taking the task's duty cycle into account.
The task_se_in_cgroup helper is functionally identical to parent_entity, but directly calling a function with that name obscures what the other code is trying to use it for, and would make the code harder to understand.
--- kernel/sched/fair.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)
kernel/sched/fair.c +26 -0
@@ -243,6 +243,7 @@ static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weightconst struct sched_class fair_sched_class;static unsigned long task_se_h_load (struct sched_entity *se); +static unsigned long task_se_h_weight (struct sched_entity *se);/************************************************************** * CFS operations on generic schedulable entities:
@@ -411,6 +412,12 @@ static inline struct sched_entity *parent_entity(struct sched_entity *se)return se->parent; } +/* Is this (task) sched_entity in a non-root cgroup? */ +static inline bool task_se_in_cgroup (struct sched_entity *se) +{ +return parent_entity (se); +} +static void find_matching_se (struct sched_entity **se,struct sched_entity **pse) {
@@ -7819,6 +7826,20 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } +static unsigned long task_se_h_weight (struct sched_entity *se) +{ +struct cfs_rq *cfs_rq; + +if (!task_se_in_cgroup (se)) +return se->load.weight; + + cfs_rq =group_cfs_rq_of_parent (se); +update_cfs_rq_h_load (cfs_rq); + +/* Reduce the load.weight by the h_load of the group the task is in. */ +return (cfs_rq->h_load * se->load.weight) >>SCHED_FIXEDPOINT_SHIFT ; +} +static unsigned long task_se_h_load (struct sched_entity *se) {struct cfs_rq *cfs_rq =group_cfs_rq_of_parent (se);
@@ -7855,6 +7876,11 @@ static unsigned long task_se_h_load(struct sched_entity *se) {return se->avg.load_avg; } + +static unsigned long task_se_h_weight (struct sched_entity *se) +{ +return se->load.weight; +}#endif /********** Helpers for find_busiest_group ************************/
Signature · 1 line
2.20.1
Re: [PATCH 09/10] sched,fair: add helper functions for flattened runqueue
Quoted 46 lines · Rik van Riel
Add helper functions to make the flattened runqueue patch a little smaller.
The
task_se_h_weightfunction is similar totask_se_h_load, but scales the task weight by the group weight, without taking the task's duty cycle into account.The
task_se_in_cgrouphelper is functionally identical toparent_entity, but directly calling a function with that name obscures what the other code is trying to use it for, and would make the code harder to understand.Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)kernel/sched/fair.c +9
-0@@ -243,6 +243,7 @@ static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weightconst struct sched_class fair_sched_class;static unsigned long task_se_h_load (struct sched_entity *se); +static unsigned long task_se_h_weight (struct sched_entity *se);/************************************************************** * CFS operations on generic schedulable entities: @@ -411,6 +412,12 @@ static inline struct sched_entity *parent_entity(struct sched_entity *se)return se->parent; } +/* Is this (task) sched_entity in a non-root cgroup? */ +static inline bool task_se_in_cgroup (struct sched_entity *se) +{ +return parent_entity (se); +} +static void find_matching_se (struct sched_entity **se,struct sched_entity **pse) {@@ -7819,6 +7826,20 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } +static unsigned long task_se_h_weight (struct sched_entity *se) +{
kernel/sched/fair.c static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) · line 7840
Quoted 10 lines
kernel/sched/fair.c +10
-0+struct cfs_rq *cfs_rq; + +if (!task_se_in_cgroup (se)) +return se->load.weight; + + cfs_rq =group_cfs_rq_of_parent (se); +update_cfs_rq_h_load (cfs_rq); + +/* Reduce the load.weight by the h_load of the group the task is in. */ +return (cfs_rq->h_load * se->load.weight) >>SCHED_FIXEDPOINT_SHIFT ;
This should be
scale_load_down(cfs_rq->h_load * se->load.weight);
Thanks,
Josef
Re: [PATCH 09/10] sched,fair: add helper functions for flattened runqueue
Quoted 19 lines · Josef Bacik
Quoted 15 lines
kernel/sched/fair.c +11
-0+static unsigned long task_se_h_weight (struct sched_entity *se) +{ +struct cfs_rq *cfs_rq; + +if (!task_se_in_cgroup (se)) +return se->load.weight; + + cfs_rq =group_cfs_rq_of_parent (se); +update_cfs_rq_h_load (cfs_rq); + +/* Reduce the load.weight by the h_load of the group the task is in. */
(quoted diff) +1
-0+ return (cfs_rq->h_load * se->load.weight) >>Quoted 1 line
SCHED_FIXEDPOINT_SHIFT;This should be
Quoted 1 line
scale_load_down(cfs_rq->h_load * se->load.weight);
That may be the same mathematically, but it is
different conceptually.
If we convert CFS to have full load resolution with cgroups (which we probably want), then scale_load_down becomes a noop, while this shift continues doing the right thing.
Signature · 1 line
All Rights Reversed.
PATCH v2 10/10 sched,fair: flatten hierarchical runqueues
In reply to Rik van RielFlatten the hierarchical runqueues into just the per CPU rq.cfs runqueue.
Iteration of the sched_entity hierarchy is rate limited to once per jiffy per sched_entity, which is a smaller change than it seems, because load average adjustments were already rate limited to once per jiffy before this patch series.
This patch breaks CONFIG_CFS_BANDWIDTH. The plan for that is to park tasks from throttled cgroups onto their cgroup runqueues, and slowly (using the GENTLE_FAIR_SLEEPERS) wake them back up, in vruntime order, once the cgroup gets unthrottled, to prevent thundering herd issues.
--- include/linux/sched.h | 2 + kernel/sched/fair.c | 452 +++++++++++++++--------------------------- kernel/sched/pelt.c | 6 +- kernel/sched/pelt.h | 2 +- kernel/sched/sched.h | 2 +- 5 files changed, 171 insertions(+), 293 deletions(-)
include/linux/sched.h +2 -0
@@ -453,6 +453,8 @@ struct sched_entity {#ifdef CONFIG_FAIR_GROUP_SCHED int depth;unsigned long enqueued_h_load; +unsigned long enqueued_h_weight; +struct load_weight h_load;struct sched_entity *parent;/* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq;
kernel/sched/fair.c +164 -288
780 lines not on this page · raw message
kernel/sched/pelt.c +3 -3
@@ -266,10 +266,10 @@ int __update_load_avg_blocked_se(u64 now, struct sched_entity *se)return 0 ; } -int __update_load_avg_se (u64 now,struct cfs_rq *cfs_rq,struct sched_entity *se) +int __update_load_avg_se (u64 now,struct cfs_rq *cfs_rq,struct sched_entity *se,bool load,bool running) { -if (___update_load_sum (now, &se->avg, !!se->on_rq, - cfs_rq->curr == se)) { +if (___update_load_sum (now, &se->avg, (!!se->on_rq || load), + (cfs_rq->curr == se) || running)) {___update_load_avg (&se->avg,se_weight (se));cfs_se_util_change (&se->avg);
kernel/sched/pelt.h +1 -1
@@ -2,7 +2,7 @@#include "sched-pelt.h" int __update_load_avg_blocked_se (u64 now,struct sched_entity *se); -int __update_load_avg_se (u64 now,struct cfs_rq *cfs_rq,struct sched_entity *se); +int __update_load_avg_se (u64 now,struct cfs_rq *cfs_rq,struct sched_entity *se,bool load,bool running);int __update_load_avg_cfs_rq (u64 now,struct cfs_rq *cfs_rq);int update_rt_rq_load_avg (u64 now,struct rq *rq,int running);int update_dl_rq_load_avg (u64 now,struct rq *rq,int running);
kernel/sched/sched.h +1 -1
@@ -1444,7 +1444,7 @@ static inline void set_task_rq(struct task_struct *p, unsigned int cpu)#ifdef CONFIG_FAIR_GROUP_SCHED set_task_rq_fair (&p->se, p->se.cfs_rq, tg->cfs_rq[cpu]); - p->se.cfs_rq = tg->cfs_rq[cpu]; + p->se.cfs_rq = &cpu_rq (cpu)->cfs; p->se.parent = tg->se[cpu];#endif
Signature · 1 line
2.20.1
Re: [PATCH 10/10] sched,fair: flatten hierarchical runqueues
Quoted 113 lines · Rik van Riel
Flatten the hierarchical runqueues into just the per CPU rq.cfs runqueue.
Iteration of the
sched_entityhierarchy is rate limited to once per jiffy persched_entity, which is a smaller change than it seems, because load average adjustments were already rate limited to once per jiffy before this patch series.This patch breaks
CONFIG_CFS_BANDWIDTH. The plan for that is to park tasks from throttled cgroups onto their cgroup runqueues, and slowly (using theGENTLE_FAIR_SLEEPERS) wake them back up, in vruntime order, once the cgroup gets unthrottled, to prevent thundering herd issues.Signed-off-by Rik van Riel <[email protected]>--- include/linux/sched.h | 2 + kernel/sched/fair.c | 452 +++++++++++++++--------------------------- kernel/sched/pelt.c | 6 +- kernel/sched/pelt.h | 2 +- kernel/sched/sched.h | 2 +- 5 files changed, 171 insertions(+), 293 deletions(-)include/linux/sched.h +2
-0@@ -453,6 +453,8 @@ struct sched_entity {#ifdef CONFIG_FAIR_GROUP_SCHED int depth;unsigned long enqueued_h_load; +unsigned long enqueued_h_weight; +struct load_weight h_load;struct sched_entity *parent;/* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq;kernel/sched/fair.c +30
-16@@ -450,6 +450,19 @@ find_matching_se(struct sched_entity **se, struct sched_entity **pse) } } +/* Add the cgroup cfs_rqs to the list, for update_blocked_averages */ +static void enqueue_entity_cfs_rqs (struct sched_entity *se) +{ +SCHED_WARN_ON (!entity_is_task (se)); + +for_each_sched_entity (se) { +struct cfs_rq *cfs_rq =group_cfs_rq_of_parent (se); + +if (list_add_leaf_cfs_rq (cfs_rq)) +break ; + } +} +#else /* !CONFIG_FAIR_GROUP_SCHED */ static inline struct task_struct *task_of (struct sched_entity *se)@@ -672,8 +685,14 @@ int sched_proc_update_handler(struct ctl_table *table, int write,*/ static inline u64 calc_delta_fair (u64 delta,struct sched_entity *se) { -if (unlikely (se->load.weight !=NICE_0_LOAD )) +if (task_se_in_cgroup (se)) { +unsigned long h_weight =task_se_h_weight (se); +if (h_weight != se->h_load.weight) +update_load_set (&se->h_load, h_weight); + delta =__calc_delta (delta,NICE_0_LOAD , &se->h_load); + }else if (unlikely (se->load.weight !=NICE_0_LOAD )) { delta =__calc_delta (delta,NICE_0_LOAD , &se->load); + }return delta; }@@ -687,22 +706,16 @@ static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)static u64 sched_slice (struct cfs_rq *cfs_rq,struct sched_entity *se) {u64 slice = sysctl_sched_latency; +struct load_weight *load = &cfs_rq->load; +struct load_weight lw; -for_each_sched_entity (se) { -struct load_weight *load; -struct load_weight lw; - - cfs_rq =cfs_rq_of (se); - load = &cfs_rq->load; +if (unlikely (!se->on_rq)) { + lw = cfs_rq->load; -if (unlikely (!se->on_rq)) { - lw = cfs_rq->load; - -update_load_add (&lw, se->load.weight); - load = &lw; - } - slice =__calc_delta (slice, se->load.weight, load); +update_load_add (&lw,task_se_h_weight (se)); + load = &lw; } + slice =__calc_delta (slice,task_se_h_weight (se), load);/* * To avoid cache thrashing, run at least sysctl_sched_min_granularity. @@ -2703,16 +2716,28 @@ static inline void update_scan_period(struct task_struct *p, int new_cpu)static void account_entity_enqueue (struct cfs_rq *cfs_rq,struct sched_entity *se) { -update_load_add (&cfs_rq->load, se->load.weight); -if (!parent_entity (se)) +struct rq *rq; + +if (task_se_in_cgroup (se)) {
kernel/sched/fair.c static inline void update_scan_period(struct task_struct *p, int new_cpu) · line 2731
Quoted 10 lines
kernel/sched/fair.c +10
-0+struct cfs_rq *cgroup_rq =group_cfs_rq_of_parent (se); +unsigned long h_weight; + +update_load_add (&cgroup_rq->load, se->load.weight); + cgroup_rq->nr_running++; + +/* Add the hierarchical weight to the CPU rq */ + h_weight =task_se_h_weight (se); + se->enqueued_h_weight = h_weight; +update_load_add (&rq_of (cfs_rq)->load, h_weight);
Ok I think this is where we need to handle the newly enqueued se's potential weight. Right now task_se_h_weight() is based on it's weight _and_ its load. So it's really it's task_se_h_weighted_load_avg, and not really task_se_h_weight, right? Instead we should separate these two things out, one gives us our heirarchal load, and one that gives us our heirarchal weight based purely on the ratio of (our weight) / (total se weight on parent). Then we can take this number and max it with the heirarchal load avg and use that with the update_load_add. Does that make sense? Thanks,
Josef
Re: [PATCH 10/10] sched,fair: flatten hierarchical runqueues
Quoted 29 lines · Josef Bacik
Quoted 11 lines · Rik van Riel
kernel/sched/fair.c +3
-2@@ -2703,16 +2716,28 @@ static inline void update_scan_period(struct task_struct *p, int new_cpu) static void account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se) { - update_load_add(&cfs_rq->load, se->load.weight); -if (!parent_entity (se)) + struct rq *rq; + +if (task_se_in_cgroup (se)) {kernel/sched/fair.c static inline void · line 2733
Quoted 10 lines
kernel/sched/fair.c +10
-0+struct cfs_rq *cgroup_rq =group_cfs_rq_of_parent (se); +unsigned long h_weight; + +update_load_add (&cgroup_rq->load, se->load.weight); + cgroup_rq->nr_running++; + +/* Add the hierarchical weight to the CPU rq */ + h_weight =task_se_h_weight (se); + se->enqueued_h_weight = h_weight; +update_load_add (&rq_of (cfs_rq)->load, h_weight);Ok I think this is where we need to handle the newly enqueued se's potential
weight. Right nowtask_se_h_weight()is based on it's weight _and_ its load.
So it's really it'stask_se_h_weighted_load_avg, and not reallytask_se_h_weight, right? Instead we should separate these two things
Quoted 8 lines
out, one
gives us our heirarchal load, and one that gives us our heirarchal weight based
purely on the ratio of (our weight) / (total se weight on parent). Then we can
take this number and max it with the heirarchal load avg and use that with theupdate_load_add. Does that make sense? Thanks,
Yes, I think that makes sense.
The hierarchical group weights can be computed periodically, in the same way the hierarchical group load averages are.
We may still end up with stale values occasionally, if the values were already computed the same jiffy, or when the values of another group (with a shared parent) have not been propagated up yet, but things should converge relatively quickly.
It means update_cfs_rq_h_load() and update_blocked_averages() will propagate both load averages and instantaneous weights, which should be easy enough to add.
I'll give it a try!
Signature · 1 line
All Rights Reversed.