sched,cfs: 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 regression with schbench, where the p99 latency goes up before the system is fully overloaded. I suspect wakeup_preempt_entity() and wakeup_gran() because they now use the task_h_load instead of the unscaled load to figure out whether a task should be preempted.
- 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.
This patch applies on top of what was Linus's current tree when I last
rebased it:2c1212de6f97 ("Merge tag 'spdx-5.2-rc2' of git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/driver-core")
include/linux/sched.h | 5 kernel/sched/core.c | 2 kernel/sched/debug.c | 12 kernel/sched/fair.c | 744 +++++++++++++++++++++----------------------------- kernel/sched/pelt.c | 55 +-- kernel/sched/pelt.h | 2 kernel/sched/sched.h | 9 7 files changed, 346 insertions(+), 483 deletions(-)
PATCH 1/8 sched: introduce task_se_h_load helper
Sometimes the hierarchical load of a sched_entity needs to be calculated. Split out task_h_load into a task_se_h_load that takes a sched_entity pointer as its argument, and a task_h_load wrapper that calls task_se_h_load.
No functional changes.
--- kernel/sched/fair.c | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-)
kernel/sched/fair.c +14 -3
@@ -706,6 +706,7 @@ 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_se_h_load (struct sched_entity *se);static unsigned long task_h_load (struct task_struct *p);static unsigned long capacity_of (int cpu);
@@ -7833,14 +7834,19 @@ 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 ); } + +static unsigned long task_h_load (struct task_struct *p) +{ +return task_se_h_load (&p->se); +}#else static inline void update_blocked_averages (int cpu) {
@@ -7865,6 +7871,11 @@ static inline void update_blocked_averages(int cpu)rq_unlock_irqrestore (rq, &rf); } +static unsigned long task_se_h_load (struct sched_entity *se) +{ +return se->avg.load_avg; +} +static unsigned long task_h_load (struct task_struct *p) {return p->se.avg.load_avg;
Signature · 1 line
2.20.1
Dietmar Eggemann
reviewerRe: [PATCH 1/8] sched: introduce task_se_h_load helper
Quoted 28 lines · Rik van Riel
Sometimes the hierarchical load of a
sched_entityneeds to be calculated. Split outtask_h_loadinto atask_se_h_loadthat takes asched_entitypointer as its argument, and atask_h_loadwrapper that callstask_se_h_load.No functional changes.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-)kernel/sched/fair.c +1
-1@@ -706,6 +706,7 @@ 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_se_h_load (struct sched_entity *se);static unsigned long task_h_load (struct task_struct *p);static unsigned long capacity_of (int cpu);@@ -7833,14 +7834,19 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } -static unsigned long task_h_load (struct task_struct *p)
kernel/sched/fair.c static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) · line 7844
Quoted 10 lines
kernel/sched/fair.c +3
-2+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 ); }
I wonder if this is necessary. I placed a BUG_ON(!entity_is_task(se)) into task_se_h_load() after I applied the whole patch-set and ran some taskgroup related testcases. It didn't hit.
So why not use task_h_load(task_of(se)) instead?
[...]
Re: [PATCH 1/8] sched: introduce task_se_h_load helper
Quoted 22 lines · Dietmar Eggemann
Quoted 6 lines
kernel/sched/fair.c +0
-1@@ -7833,14 +7834,19 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } -static unsigned long task_h_load (struct task_struct *p)kernel/sched/fair.c static void update_cfs_rq_h_load(struct · line 7845
Quoted 10 lines
kernel/sched/fair.c +3
-2+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 ); }I wonder if this is necessary. I placed a BUG_ON(!entity_is_task(se)) into
task_se_h_load()after I applied the whole patch-set and ran some
taskgroup related testcases. It didn't hit.
Quoted 3 lines
So why not use task_h_load(task_of(se)) instead?
[...]
That would work, but task_h_load then dereferences task->se to get the se->avg.load_avg value.
Going back to task from the se, only to then get the se from the task seems a little unnecessary :)
Can you explain why you think task_h_load(task_of(se)) would be better? I think I may be overlooking something.
Signature · 1 line
All Rights Reversed.
Dietmar Eggemann
reviewerRe: [PATCH 1/8] sched: introduce task_se_h_load helper
Quoted 28 lines · Rik van Riel
Quoted 22 lines · Dietmar Eggemann
Quoted 6 lines
kernel/sched/fair.c +0
-1@@ -7833,14 +7834,19 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) } } -static unsigned long task_h_load (struct task_struct *p)kernel/sched/fair.c static void update_cfs_rq_h_load(struct · line 7845
Quoted 10 lines
kernel/sched/fair.c +3
-2+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 ); }I wonder if this is necessary. I placed a BUG_ON(!entity_is_task(se)) into
task_se_h_load()after I applied the whole patch-set and ran some
taskgroup related testcases. It didn't hit.Quoted 3 lines
So why not use task_h_load(task_of(se)) instead?
[...]
Quoted 8 lines
That would work, but
task_h_loadthen dereferencestask->seto get these->avg.load_avgvalue.Going back to task from the se, only to then get the se from the task seems a little unnecessary :)
Can you explain why you think task_h_load(task_of(se)) would be better? I think I may be overlooking something.
Ah, OK, I just wanted to avoid having task_se_h_load() and task_h_load() at the same time. You could replace the remaining calls to task_h_load(p) with task_se_h_load(&p->se) in this case.
- task_load = task_h_load(p);
+ task_load = task_se_h_load(&p->se);
Not that important though right now ...
Re: [PATCH 1/8] sched: introduce task_se_h_load helper
Quoted 16 lines · Dietmar Eggemann
Quoted 8 lines · Rik van Riel
That would work, but
task_h_loadthen dereferencestask->seto get these->avg.load_avgvalue.Going back to task from the se, only to then get the se from the task seems a little unnecessary :)
Can you explain why you think task_h_load(task_of(se)) would be better? I think I may be overlooking something.
Ah, OK, I just wanted to avoid having
task_se_h_load()andtask_h_load()
at the same time. You could replace the remaining calls totask_h_load(p)withtask_se_h_load(&p->se)in this case.
Quoted 4 lines
-
task_load=task_h_load(p);
+task_load=task_se_h_load(&p->se);Not that important though right now ...
That I can do.
I might as well do that while going through the rest of the series to merge in the bug fix that I have for the performance regression, and the fixes for compilation with other config options.
Thank you for the suggestion.
Signature · 1 line
All Rights Reversed.
PATCH 2/8 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
@@ -419,11 +419,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
@@ -541,7 +539,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",
@@ -550,17 +547,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
@@ -964,10 +959,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
PATCH 3/8 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. lhen switching to a flat runqueue, that no longer works.
Redefine the CPU cfs_rq runnable_load_avg to be the sum of task_h_loads of the runnable tasks. 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
@@ -965,6 +965,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
Dietmar Eggemann
reviewerRe: [PATCH 3/8] sched,fair: redefine runnable_load_avg as the sum of task_h_load
Hi Rik,
On 6/12/19 9:32 PM, Rik van Riel wrote:
[...]
Quoted 4 lines
kernel/sched/pelt.c +0
-0@@ -379,17 +368,11 @@ int update_irq_load_avg(struct rq *rq, u64 running)* We can safely remove running from rq->clock because * rq->clock += delta with delta >= running */
kernel/sched/pelt.c int update_irq_load_avg(struct rq *rq, u64 running) · line 372
Quoted 10 lines
kernel/sched/pelt.c +2
-8- ret =___update_load_sum (rq->clock - running, &rq->avg_irq, -0 , -0 , -0 ); - ret +=___update_load_sum (rq->clock, &rq->avg_irq, -1 , -1 , -1 ); + ret =___update_load_sum (rq->clock - running, &rq->avg_irq,0 ); + ret +=___update_load_sum (rq->clock, &rq->avg_irq,1 );
The 'int running' argument in the two ___update_load_sum() calls is missing. Doesn't compile for me (arm64 defconfig w/ CONFIG_IRQ_TIME_ACCOUNTING=y).
[...]
Dietmar Eggemann
reviewerRe: [PATCH 3/8] sched,fair: redefine runnable_load_avg as the sum of task_h_load
In reply to Rik van RielQuoted 2 lines · Rik van Riel
The
runnable_loadmagic is used to quickly propagate information about runnable tasks up the hierarchy of runqueues. lhen switching to a flat
Looks like here is some information missing.
Quoted 28 lines
runqueue, that no longer works.
Redefine the CPU
cfs_rqrunnable_load_avgto be the sum oftask_h_loadsof the runnable tasks. This provides enough information to the load balancer.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.
Signed-off-by Rik van Riel <[email protected]>--- 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 +0
-0
include/linux/sched.h struct util_est { · line 396
Quoted 7 lines
include/linux/sched.h +0
-1@@ -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;
Could you not also remove runnable_load_avg from struct sched_avg and put it into the struct cfs_rq directly. The signal has nothing to to with PELT anymore and se don't have to carry it. You only need it for the root cfs_rq's but it's at least better than having it still for all se's as well.
[...]
include/linux/sched.h account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 2769
Quoted 7 lines
include/linux/sched.h +2
-1@@ -2767,20 +2765,39 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)static inline void enqueue_runnable_load_avg (struct cfs_rq *cfs_rq,struct sched_entity *se) { - cfs_rq->runnable_weight += se->runnable_weight; +if (entity_is_task (se)) { +struct cfs_rq *cpu_cfs_rq = &cfs_rq->rq->cfs;
There are a couple of comments in fair.c referring to this cfs_rq as the root cfs_rq, rather the cpu cfs_rq. IMHO, easier to read if we stick to one name (root_cfs_rq vs. cpu_cfs_rq).
[...]
PATCH 4/8 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
@@ -285,6 +285,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
@@ -310,6 +317,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; }
@@ -358,6 +366,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 ; }
@@ -7688,6 +7701,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
@@ -556,6 +556,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
PATCH 5/8 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
@@ -275,6 +275,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q; } +/* runqueue owned by the parent entity */ +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)->rq->cfs; +} +static inline bool list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq) {struct rq *rq =rq_of (cfs_rq);
@@ -3298,7 +3307,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);
@@ -7779,7 +7788,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 ;
@@ -7802,7 +7811,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,
@@ -10159,7 +10168,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
Dietmar Eggemann
reviewerRe: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper
Quoted 41 lines · Rik van Riel
Use an explicit "
cfs_rqof parentsched_entity" helper in a few strategic places, wherecfs_rq_of(se)may no longer point at the right runqueue once we flatten the hierarchical cgroup runqueues.No functional change.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-)kernel/sched/fair.c +10
-1@@ -275,6 +275,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q; } +/* runqueue owned by the parent entity */ +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)->rq->cfs; +} +static inline bool list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq) {struct rq *rq =rq_of (cfs_rq);@@ -3298,7 +3307,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);
kernel/sched/fair.c static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) · line 7791
Quoted 5 lines
kernel/sched/fair.c +1
-1@@ -7779,7 +7788,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);
Why do you change this here? task_se_h_load() calls update_cfs_rq_h_load() with cfs_rq = group_cfs_rq_of_parent(se) because the task might not be on the cfs_rq yet.
But inside update_cfs_rq_h_load() the first se is derived from cfs_rq->tg->se[cpu_of(rq)] so in the first for_each_sched_entity() loop we should still start with group_cfs_rq() (se->my_q) ?
The system doesn't barf with these two WARN_ON's in.
@@ -7663,12 +7673,17 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
unsigned long now = jiffies;
unsigned long load;+ WARN_ON(se && (se != group_cfs_rq(se)->tg->se[cpu_of(rq)]));
+
if (cfs_rq->last_h_load_update == now)
return;
WRITE_ONCE(cfs_rq->h_load_next, NULL);
for_each_sched_entity(se) {
cfs_rq = group_cfs_rq_of_parent(se);
+
+ WARN_ON(se != group_cfs_rq(se)->tg->se[cpu_of(rq)]);
+
WRITE_ONCE(cfs_rq->h_load_next, se);
if (cfs_rq->last_h_load_update == now)
break;[...]
Re: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper
Quoted 47 lines · Dietmar Eggemann
Quoted 46 lines · Rik van Riel
Use an explicit "
cfs_rqof parentsched_entity" helper in a few strategic places, wherecfs_rq_of(se)may no longer point at the right runqueue once we flatten the hierarchical cgroup runqueues.No functional change.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-)kernel/sched/fair.c +9
-0@@ -275,6 +275,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q; } +/* runqueue owned by the parent entity */ +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)->rq->cfs; +} +static inline bool list_add_leaf_cfs_rq (struct cfs_rq *cfs_rq){
kernel/sched/fair.c +1
-1struct rq *rq =rq_of (cfs_rq);@@ -3298,7 +3307,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);@@ -7779,7 +7788,7 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
Quoted 9 lines
kernel/sched/fair.c static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) · line 7791
Quoted 4 lines
kernel/sched/fair.c +1
-1WRITE_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);Why do you change this here?
task_se_h_load()callsupdate_cfs_rq_h_load()withcfs_rq=group_cfs_rq_of_parent(se)because
the task might not be on thecfs_rqyet.
Because patch 6 points cfs_rq_of(se) at the CPU's top level cfs_rq for every task se ...
... but I guess since I have not changed where the cfs_rq_of points for cgroup sched_entities, this change is not necessary at this time, and I should be able to go without it, in this function.
Quoted 32 lines
But inside
update_cfs_rq_h_load()the first se is derived from cfs_rq->tg->se[cpu_of(rq)] so in the firstfor_each_sched_entity()loop
we should still start withgroup_cfs_rq()(se->my_q) ?The system doesn't barf with these two WARN_ON's in.
(quoted diff) +0
-0@@ -7663,12 +7673,17 @@ static void update_cfs_rq_h_load(struct
cfs_rq*cfs_rq)unsigned long now = jiffies; unsigned long load;(quoted diff) +5
-0+ WARN_ON(se && (se != group_cfs_rq(se)->tg->se[cpu_of(rq)])); + if (cfs_rq->last_h_load_update == now) return; WRITE_ONCE(cfs_rq->h_load_next, NULL); for_each_sched_entity(se) { cfs_rq = group_cfs_rq_of_parent(se); + + WARN_ON(se != group_cfs_rq(se)->tg->se[cpu_of(rq)]); + WRITE_ONCE(cfs_rq->h_load_next, se); if (cfs_rq->last_h_load_update == now) break;
Signature · 1 line
All Rights Reversed.
Dietmar Eggemann
reviewerRe: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper
Quoted 2 lines · Rik van Riel
Quoted 1 line · Dietmar Eggemann
On 6/12/19 9:32 PM, Rik van Riel wrote:
[...]
Quoted 13 lines
Quoted 12 lines
kernel/sched/fair.c static void update_cfs_rq_h_load(struct · line 7792
Quoted 7 lines
kernel/sched/fair.c +1
-1@@ -7779,7 +7788,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);Why do you change this here?
task_se_h_load()callsupdate_cfs_rq_h_load()withcfs_rq=group_cfs_rq_of_parent(se)because
the task might not be on thecfs_rqyet.
Quoted 7 lines
Because patch 6 points
cfs_rq_of(se)at the CPU's top levelcfs_rqfor every task se ...... but I guess since I have not changed where the
cfs_rq_ofpoints for cgroupsched_entities, this change is not necessary at this time, and I should be able to go without it, in this function.
IMHO, since you only change set_task_rq() (p->se.cfs_rq = &cpu_rq(cpu)->cfs instead of tg->cfs_rq[cpu] in 8/8) (used for a task) and not init_tg_cfs_entry() (used for a taskgroup), 'cfs_rq_of(se) == se->parent->my_q' should still be true in update_cfs_rq_h_load().
update_cfs_rq_h_load() only deals with se's representing taskgroups. So cfs_rq_of(se) and group_cfs_rq_of_parent(se) should deliver the same result for these se's.
Quoted 4 lines
Quoted 4 lines
But inside
update_cfs_rq_h_load()the first se is derived from cfs_rq->tg->se[cpu_of(rq)] so in the firstfor_each_sched_entity()loop
we should still start withgroup_cfs_rq()(se->my_q) ?
Here I was wrong. The first loop did use cfs_rq_of() and not group_cfs_rq(). [...]
Dietmar Eggemann
reviewerRe: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper
In reply to Rik van RielQuoted 16 lines · Rik van Riel
Use an explicit "
cfs_rqof parentsched_entity" helper in a few strategic places, wherecfs_rq_of(se)may no longer point at the right runqueue once we flatten the hierarchical cgroup runqueues.No functional change.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-)kernel/sched/fair.c +0
-0
kernel/sched/fair.c static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp) · line 284
Quoted 10 lines
kernel/sched/fair.c +7
-0@@ -275,6 +275,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q; } +/* runqueue owned by the parent entity */ +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)->rq->cfs;
The function name and the description is not 100% correct. For tasks running naturally (not in a flattened taskgroup) in the root taskgroup or for the se representing a first level taskgroup (e.g. /tg1 (with se->depth = 0)) it returns the root cfs_rq or easier se->cfs_rq.
So you could replace
return &cfs_rq_of(se)->rq->cfs;
with
return se->cfs_rq;
or
return cfs_rq_of(se);
I guess a crucial point to understand is that you do need both, cfs_rq_of(se) to access the flattened and group_cfs_rq_of_parent(se) to access the hierarchical world.
[...]
Re: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper
Quoted 40 lines · Dietmar Eggemann
Quoted 18 lines · Rik van Riel
Use an explicit "
cfs_rqof parentsched_entity" helper in a few strategic places, wherecfs_rq_of(se)may no longer point at the right runqueue once we flatten the hierarchical cgroup runqueues.No functional change.
Signed-off-by Rik van Riel <[email protected]>--- kernel/sched/fair.c | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-)kernel/sched/fair.c +0
-0@@ -275,6 +275,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)return grp->my_q;kernel/sched/fair.c static inline struct cfs_rq · line 286
Quoted 10 lines
kernel/sched/fair.c +7
-0} +/* runqueue owned by the parent entity */ +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)->rq->cfs;The function name and the description is not 100% correct. For tasks running naturally (not in a flattened taskgroup) in the root taskgroup
or for the se representing a first level taskgroup (e.g. /tg1 (withse->depth= 0)) it returns the rootcfs_rqor easierse->cfs_rq.So you could replace
return &cfs_rq_of(se)->rq->cfs;
Quoted 7 lines
with
return se->cfs_rq;or
return cfs_rq_of(se);
Good point. I will do that for the v2 series.
Signature · 1 line
All Rights Reversed.
PATCH 6/8 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
@@ -670,22 +670,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.
@@ -694,7 +678,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;
@@ -711,6 +695,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
PATCH 7/8 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 | 65 +++++++++++++++++++++++++++++---------------- 1 file changed, 42 insertions(+), 23 deletions(-)
kernel/sched/fair.c +42 -23
@@ -3481,17 +3481,17 @@ 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; +int decayed, updated =0 ;/* * 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 */ if (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) -__update_load_avg_se (now, cfs_rq, se); + updated =__update_load_avg_se (now, cfs_rq, se); decayed =update_cfs_rq_load_avg (now, cfs_rq); decayed |=propagate_entity_load_avg (se);
@@ -3510,6 +3510,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 | updated; }#ifndef CONFIG_64BIT
@@ -3851,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) {
@@ -3875,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);
@@ -3951,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.
@@ -3967,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);
@@ -3991,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
@@ -5157,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);/*
@@ -5239,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 8/8 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 | 478 +++++++++++++++++------------------------- kernel/sched/pelt.c | 6 +- kernel/sched/pelt.h | 2 +- kernel/sched/sched.h | 2 +- 5 files changed, 194 insertions(+), 296 deletions(-)
include/linux/sched.h +2 -0
@@ -454,6 +454,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 +187 -291
836 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
@@ -1443,7 +1443,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
Dietmar Eggemann
reviewerRe: [PATCH 8/8] sched,fair: flatten hierarchical runqueues
On 6/12/19 9:32 PM, Rik van Riel wrote:
[...]
kernel/sched/fair.c static inline struct sched_entity *parent_entity(struct sched_entity *se) · line 418
Quoted 8 lines
kernel/sched/fair.c +4
-0@@ -410,6 +412,11 @@ static inline struct sched_entity *parent_entity(struct sched_entity *se)return se->parent; } +static inline bool task_se_in_cgroup (struct sched_entity *se) +{ +return parent_entity (se); +}
IMHO, s/in_cgroup/not_in_root_tg/ reads easier. "/", i.e. the root tg is still a cgroup, I guess. But you could use existing parent_entity(se) as well.
[...]
Quoted 17 lines
kernel/sched/fair.c +4
-7@@ -679,22 +710,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; +if (unlikely (!se->on_rq)) { + lw = cfs_rq->load; - cfs_rq =cfs_rq_of (se); - load = &cfs_rq->load; - -if (unlikely (!se->on_rq)) {
kernel/sched/fair.c static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) · line 722
Quoted 10 lines
kernel/sched/fair.c +3
-6- 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_load (se)); + load = &lw; } + slice =__calc_delta (slice,task_se_h_load (se), load);
task_se_h_load(se) and se->load.weight are off my factor of >= 1024 on 64bit.
...
bash pid=3250: task_se_h_load(se)=1023 se->load.weight=1048576
sysctl_sched_latency=18000000 slice=0 old_slice=17999995...
[...]
Re: [PATCH 8/8] sched,fair: flatten hierarchical runqueues
Quoted 9 lines · Dietmar Eggemann
On 6/12/19 9:32 PM, Rik van Riel wrote:
[...]
Quoted 5 lines
kernel/sched/fair.c +0
-0@@ -410,6 +412,11 @@ static inline struct sched_entity *parent_entity(struct sched_entity *se)return se->parent; }
Quoted 10 lines
kernel/sched/fair.c static inline struct sched_entity *parent_entity(struct sched_entity *se) · line 418
Quoted 4 lines
kernel/sched/fair.c +4
-0+static inline bool task_se_in_cgroup (struct sched_entity *se) +{ +return parent_entity (se); +}IMHO, s/in_cgroup/not_in_root_tg/ reads easier. "/", i.e. the root tg is
still a cgroup, I guess. But you could use existingparent_entity(se)as
well.
I agree my name is not the prettiest, but I am not entirely convinced your idea is an improvement.
I'll hold out for better ideas by other reviewers :)
Quoted 25 lines
Quoted 25 lines
kernel/sched/fair.c +4
-13@@ -679,22 +710,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; +if (unlikely (!se->on_rq)) { + lw = cfs_rq->load; - cfs_rq =cfs_rq_of (se); - load = &cfs_rq->load; - -if (unlikely (!se->on_rq)) { - lw = cfs_rq->load; - -update_load_add (&lw, se->load.weight); - load = &lw; - } - slice =__calc_delta (slice, se->load.weight, load);
Quoted 8 lines
kernel/sched/fair.c static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se) · line 722
Quoted 4 lines
kernel/sched/fair.c +3
-0+update_load_add (&lw,task_se_h_load (se)); + load = &lw; } + slice =__calc_delta (slice,task_se_h_load (se), load);
task_se_h_load(se)andse->load.weightare off my factor of >= 1024 on
64bit.
Oh indeed they are!
I wonder if this is the root cause of that performance regression I have been hunting for the past few weeks :)
Let me go test some things...
Quoted 7 lines
...
bash pid=3250: task_se_h_load(se)=1023 se->load.weight=1048576 sysctl_sched_latency=18000000 slice=0 old_slice=17999995...
[...]
Signature · 1 line
All Rights Reversed.
Dietmar Eggemann
reviewerRe: [PATCH 8/8] sched,fair: flatten hierarchical runqueues
In reply to Rik van RielQuoted 21 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 | 478 +++++++++++++++++------------------------- kernel/sched/pelt.c | 6 +- kernel/sched/pelt.h | 2 +- kernel/sched/sched.h | 2 +- 5 files changed, 194 insertions(+), 296 deletions(-)
[...]
Quoted 1 line
kernel/sched/fair.c +0
-0
[...]
kernel/sched/fair.c static inline bool update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s · line 3547
Quoted 6 lines
kernel/sched/fair.c +1
-1@@ -3491,7 +3544,7 @@ static inline bool update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s* track group sched_entity load average for task_h_load calc in migration */ if (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) - updated =__update_load_avg_se (now, cfs_rq, se); + updated =__update_load_avg_se (now, cfs_rq, se, curr, curr);
I wonder if task migration is still working correctly.
migrate_task_rq_fair(p, ...) -> remove_entity_load_avg(&p->se) would use cfs_rq = se->cfs_rq (i.e. root cfs_rq). So load (and util) will not propagate through the taskgroup hierarchy.
[...]
Re: [PATCH 8/8] sched,fair: flatten hierarchical runqueues
Quoted 49 lines · Dietmar Eggemann
Quoted 29 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 | 478 +++++++++++++++++--------------------- ---- kernel/sched/pelt.c | 6 +- kernel/sched/pelt.h | 2 +- kernel/sched/sched.h | 2 +- 5 files changed, 194 insertions(+), 296 deletions(-)[...]
Quoted 1 line
kernel/sched/fair.c +0
-0[...]
Quoted 9 lines
kernel/sched/fair.c +0
-0@@ -3491,7 +3544,7 @@ static inline bool update_load_avg(struct
cfs_rq*cfs_rq, structsched_entity*s
* track groupsched_entityload average fortask_h_loadcalc
in migrationkernel/sched/fair.c +1
-1*/ if (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) - updated =__update_load_avg_se (now, cfs_rq, se); + updated = __update_load_avg_se(now, cfs_rq, se, curr,curr);
I wonder if task migration is still working correctly.
Quoted 6 lines
migrate_task_rq_fair(p, ...)->remove_entity_load_avg(&p->se)would usecfs_rq=se->cfs_rq(i.e. rootcfs_rq). So load (and util) will not propagate through the taskgroup hierarchy.[...]
Good point. This should be the group cfs_rq, and
then on the next tick the load change will be
propagated up.
Let me add that change in for v2 as well.
Signature · 1 line
All Rights Reversed.