sched: add multiple hierarchy support to the CFS group scheduler
cover sched: add multiple hierarchy support to the CFS group scheduler
Hi Ingo,
These patches change the fairness model as discussed in
http://lkml.org/lkml/2008/1/30/634
Patch 1 -> Changes the fairness model
Patch 2 -> Allows one to create multiple levels of cgroups
The second patch is not very good with SMP yet, that is the next TODO. Also it changes the behaviour of fair user. The root task group is the parent task group and the other users are its children.
Thanks,
Signature · 2 lines
regards, Dhaval
RFC PATCH 1/2 sched: change the fairness model of the CFS group scheduler
This patch allows tasks and groups to exist in the same cfs_rq. With this change the CFS group scheduling follows a 1/(M+N) model from a 1/(1+N) fairness model where M tasks and N groups exist at the cfs_rq level.
--- kernel/sched.c | 46 +++++++++++++++++++++ kernel/sched_fair.c | 113 +++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 137 insertions(+), 22 deletions(-)
kernel/sched.c +46 -0
@@ -224,10 +224,13 @@ struct task_group { };#ifdef CONFIG_FAIR_GROUP_SCHED + +#ifdef CONFIG_USER_SCHED /* Default task group's sched entity on each cpu */ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; +#endif static struct sched_entity *init_sched_entity_p[NR_CPUS ];static struct cfs_rq *init_cfs_rq_p[NR_CPUS ];
@@ -7163,6 +7166,10 @@ static void init_tg_cfs_entry(struct rqlist_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se; +/* se could be NULL for init_task_group */ +if (!se) +return ; + se->cfs_rq = &rq->cfs; se->my_q = cfs_rq; se->load.weight = tg->shares;
@@ -7217,11 +7224,46 @@ void __init sched_init(void)#ifdef CONFIG_FAIR_GROUP_SCHED init_task_group.shares = init_task_group_load;INIT_LIST_HEAD (&rq->leaf_cfs_rq_list); +#ifdef CONFIG_CGROUP_SCHED +/* +* How much cpu bandwidth does init_task_group get? +* +* In case of task-groups formed thr' the cgroup filesystem, it +* gets 100% of the cpu resources in the system. This overall +* system cpu resource is divided among the tasks of +* init_task_group and its child task-groups in a fair manner, +* based on each entity's (task or task-group's) weight +* (se->load.weight). +* +* In other words, if init_task_group has 10 tasks of weight +* 1024) and two child groups A0 and A1 (of weight 1024 each), +* then A0's share of the cpu resource is: +* +* A0's bandwidth = 1024 / (10*1024 + 1024 + 1024) = 8.33% +* +* We achieve this by letting init_task_group's tasks sit +* directly in rq->cfs (i.e init_task_group->se[] = NULL). +*/ +init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 ); +#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed. +* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );#endif +#endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_RT_GROUP_SCHED init_task_group.rt_runtime = sysctl_sched_rt_runtime *NSEC_PER_USEC ;
@@ -7435,6 +7477,10 @@ static int rebalance_shares(struct schedunsigned long total_load =0 , total_shares;struct task_group *tg = cfs_rq->tg; +/* Skip this group if there is no associated group entity */ +if (unlikely (!tg->se[this_cpu])) +continue ; +/* Gather total task load of this group across cpus */ for_each_cpu_mask (i, sdspan) total_load += tg->cfs_rq[i]->load.weight;
kernel/sched_fair.c +91 -22
172 lines not on this page · raw message
Signature · 2 lines
regards, Dhaval
RFC PATCH 1/2 sched: allow the CFS group scheduler to have multiple levels
In reply to Dhaval GianiThis patch makes the group scheduler multi hierarchy aware.
--- include/linux/sched.h | 2 +- kernel/sched.c | 41 ++++++++++++++++++++++++----------------- 2 files changed, 25 insertions(+), 18 deletions(-)
include/linux/sched.h +1 -1
@@ -2031,7 +2031,7 @@ extern void normalize_rt_tasks(void);extern struct task_group init_task_group; -extern struct task_group *sched_create_group (void ); +extern struct task_group *sched_create_group (struct task_group *parent);extern void sched_destroy_group (struct task_group *tg);extern void sched_move_task (struct task_struct *tsk);#ifdef CONFIG_FAIR_GROUP_SCHED
kernel/sched.c +24 -17
102 lines not on this page · raw message
Signature · 2 lines
regards, Dhaval
Re: [RFC, PATCH 1/2] sched: allow the CFS group scheduler to have multiple levels
Meant 2/2 in $subject.
Signature · 2 lines
regards, Dhaval
Re: [RFC, PATCH 1/2] sched: change the fairness model of the CFS group scheduler
In reply to Dhaval GianiQuoted 50 lines · Dhaval Giani
This patch allows tasks and groups to exist in the same
cfs_rq. With this change the CFS group scheduling follows a 1/(M+N) model from a 1/(1+N) fairness model where M tasks and N groups exist at thecfs_rqlevel.Signed-off-by Dhaval Giani <[email protected]>Signed-off-by Srivatsa Vaddagiri <[email protected]>--- kernel/sched.c | 46 +++++++++++++++++++++ kernel/sched_fair.c | 113 +++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 137 insertions(+), 22 deletions(-)Index:
linux-2.6.25-rc2/kernel/sched.c
===================================================================kernel/sched.c +13
-0@@ -224,10 +224,13 @@ struct task_group { };#ifdef CONFIG_FAIR_GROUP_SCHED + +#ifdef CONFIG_USER_SCHED /* Default task group's sched entity on each cpu */ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; +#endif static struct sched_entity *init_sched_entity_p[NR_CPUS ];static struct cfs_rq *init_cfs_rq_p[NR_CPUS ];@@ -7163,6 +7166,10 @@ static void init_tg_cfs_entry(struct rqlist_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se; +/* se could be NULL for init_task_group */ +if (!se) +return ; + se->cfs_rq = &rq->cfs; se->my_q = cfs_rq; se->load.weight = tg->shares;@@ -7217,11 +7224,46 @@ void __init sched_init(void)#ifdef CONFIG_FAIR_GROUP_SCHED init_task_group.shares = init_task_group_load;INIT_LIST_HEAD (&rq->leaf_cfs_rq_list); +#ifdef CONFIG_CGROUP_SCHED +/* +* How much cpu bandwidth does init_task_group get? +* +* In case of task-groups formed thr' the cgroup filesystem, it +* gets 100% of the cpu resources in the system. This overall
kernel/sched.c void __init sched_init(void) · line 7242
Quoted 10 lines
kernel/sched.c +10
-0+* system cpu resource is divided among the tasks of +* init_task_group and its child task-groups in a fair manner, +* based on each entity's (task or task-group's) weight +* (se->load.weight). +* +* In other words, if init_task_group has 10 tasks of weight +* 1024) and two child groups A0 and A1 (of weight 1024 each), +* then A0's share of the cpu resource is: +* +* A0's bandwidth = 1024 / (10*1024 + 1024 + 1024) = 8.33%
Cool, this is precisely what I'd expect and was hoping to see.
thanks,
-serge
Quoted 224 lines
kernel/sched.c +23
-0+* +* We achieve this by letting init_task_group's tasks sit +* directly in rq->cfs (i.e init_task_group->se[] = NULL). +*/ +init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 ); +#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed. +* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );#endif +#endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_RT_GROUP_SCHED init_task_group.rt_runtime = sysctl_sched_rt_runtime *NSEC_PER_USEC ;@@ -7435,6 +7477,10 @@ static int rebalance_shares(struct schedunsigned long total_load =0 , total_shares;struct task_group *tg = cfs_rq->tg; +/* Skip this group if there is no associated group entity */ +if (unlikely (!tg->se[this_cpu])) +continue ; +/* Gather total task load of this group across cpus */ for_each_cpu_mask (i, sdspan) total_load += tg->cfs_rq[i]->load.weight;Index:
linux-2.6.25-rc2/kernel/sched_fair.c
===================================================================kernel/sched_fair.c +91
-22@@ -732,6 +732,21 @@ static inline struct sched_entity *paren return se->parent; } +/* return the cpu load contributed by a given group on a given cpu */ +static inline unsigned long group_cpu_load (struct task_group *tg,int cpu) +{ +struct sched_entity *se = tg->se[cpu], *top_se; +struct cfs_rq *cfs_rq = tg->cfs_rq[cpu]; + +if (unlikely (!se)) +return cfs_rq->load.weight; + +for_each_sched_entity (se) + top_se = se; + +return top_se->load.weight; +} +#define GROUP_IMBALANCE_PCT 20#else /* CONFIG_FAIR_GROUP_SCHED */ @@ -1073,6 +1088,17 @@ out_set_cpu: }#endif /* CONFIG_SMP */ +/* return depth at which a sched entity is present in the hierarchy */ +static inline int depth_se (struct sched_entity *se) +{ +int depth =0 ; + +for_each_sched_entity (se) + depth++; + +return depth; +} +/* * Preempt the current task with a newly woken task if needed: @@ -1083,6 +1109,7 @@ static void check_preempt_wakeup(structstruct cfs_rq *cfs_rq =task_cfs_rq (curr);struct sched_entity *se = &curr->se, *pse = &p->se;unsigned long gran; +int se_depth, pse_depth;if (unlikely (rt_prio (p->prio))) {update_rq_clock (rq);@@ -1100,6 +1127,27 @@ static void check_preempt_wakeup(structif (!sched_feat (WAKEUP_PREEMPT ))return ; +/* +* preemption test can be made between sibling entities who are in the +* same cfs_rq i.e who have a common parent. Walk up the hierarchy of +* both tasks untill we find their ancestors who are siblings of common +* parent. +*/ + +/* First walk up until both entities are at same depth */ + se_depth =depth_se (se); + pse_depth =depth_se (pse); + +while (se_depth > pse_depth) { + se_depth--; + se =parent_entity (se); + } + +while (pse_depth > se_depth) { + pse_depth--; + pse =parent_entity (pse); + } +while (!is_same_group (se, pse)) { se =parent_entity (se); pse =parent_entity (pse);@@ -1166,13 +1214,22 @@ static void put_prev_task_fair(struct rqstatic struct task_struct *__load_balance_iterator (struct cfs_rq *cfs_rq,struct rb_node *curr) { -struct task_struct *p; +struct task_struct *p =NULL ; +struct sched_entity *se;if (!curr)return NULL ; - p = rb_entry(curr, struct task_struct, se.run_node); - cfs_rq->rb_load_balance_curr =rb_next (curr); +/* Skip over entities that are not tasks */ +do { + se = rb_entry(curr, struct sched_entity, run_node); + curr =rb_next (curr); + }while (curr && !entity_is_task (se)); + + cfs_rq->rb_load_balance_curr = curr; + +if (entity_is_task (se)) + p =task_of (se);return p; }@@ -1210,21 +1267,28 @@ load_balance_fair(struct rq *this_rq, instruct cfs_rq *this_cfs_rq = busy_cfs_rq->tg->cfs_rq[this_cpu];unsigned long maxload, task_load, group_weight;unsigned long thisload, per_task_load; -struct sched_entity *se = busy_cfs_rq->tg->se[busiest->cpu]; +struct task_group *tg = busy_cfs_rq->tg; +struct sched_entity *se = tg->se[busiest->cpu], + *this_se = tg->se[this_cpu]; task_load = busy_cfs_rq->load.weight; - group_weight = se->load.weight; +if (!task_load) +continue ; + + group_weight =group_cpu_load (tg, busiest->cpu);/* -* 'group_weight' is contributed by tasks of total weight +* 'group_weight' is contributed by entities of total weight * 'task_load'. To move 'rem_load_move' worth of weight only, * we need to move a maximum task load of: * * maxload = (remload / group_weight) * task_load; */ maxload = (rem_load_move * task_load) / group_weight; +if (!maxload) +continue ; -if (!maxload || !task_load) +if (!busy_cfs_rq->nr_running)continue ; per_task_load = task_load / busy_cfs_rq->nr_running;@@ -1253,23 +1317,28 @@ load_balance_fair(struct rq *this_rq, in &cfs_rq_iterator);#ifdef CONFIG_FAIR_GROUP_SCHED -/* -* load_moved holds the task load that was moved. The -* effective (group) weight moved would be: -* load_moved_eff = load_moved/task_load * group_weight; -*/ - load_moved = (group_weight * load_moved) / task_load; -/* Adjust shares on both cpus to reflect load_moved */ - group_weight -= load_moved; -set_se_shares (se, group_weight); +if (likely (se)) { +unsigned long load_moved_eff; +unsigned long se_shares; - se = busy_cfs_rq->tg->se[this_cpu]; -if (!thisload) - group_weight = load_moved; -else - group_weight = se->load.weight + load_moved; -set_se_shares (se, group_weight); +/* +* load_moved holds the task load that was moved. The +* effective (group) weight moved would be: +* load_moved_eff = load_moved/task_load * +* group_weight; +*/ + load_moved_eff = (se->load.weight * + load_moved) / task_load; + +set_se_shares (se, se->load.weight - load_moved_eff); +if (!thisload) + se_shares = load_moved_eff; +else + se_shares = this_se->load.weight + + load_moved_eff; +set_se_shares (this_se, se_shares); + }#endif rem_load_move -= load_moved;Signature · 2 lines
regards, Dhaval
Re: [RFC, PATCH 1/2] sched: allow the CFS group scheduler to have multiple levels
In reply to Dhaval GianiQuoted 1 line · Dhaval Giani
This patch makes the group scheduler multi hierarchy aware.
Ok, good thing to do in principle
Quoted 40 lines
Signed-off-by Dhaval Giani <[email protected]>--- include/linux/sched.h | 2 +- kernel/sched.c | 41 ++++++++++++++++++++++++----------------- 2 files changed, 25 insertions(+), 18 deletions(-)Index:
linux-2.6.25-rc2/include/linux/sched.h
===================================================================include/linux/sched.h +1
-1@@ -2031,7 +2031,7 @@ extern void normalize_rt_tasks(void);extern struct task_group init_task_group; -extern struct task_group *sched_create_group (void ); +extern struct task_group *sched_create_group (struct task_group *parent);extern void sched_destroy_group (struct task_group *tg);extern void sched_move_task (struct task_struct *tsk);#ifdef CONFIG_FAIR_GROUP_SCHED Index:
linux-2.6.25-rc2/kernel/sched.c
===================================================================kernel/sched.c +4
-3@@ -7155,10 +7155,11 @@ static void init_rt_rq(struct rt_rq *rt_ }#ifdef CONFIG_FAIR_GROUP_SCHED -static void init_tg_cfs_entry (struct rq *rq,struct task_group *tg, -struct cfs_rq *cfs_rq,struct sched_entity *se, -int cpu,int add) +static void init_tg_cfs_entry (struct task_group *tg,struct cfs_rq *cfs_rq, +struct sched_entity *se,int cpu,int add, +struct sched_entity *parent) { +struct rq *rq =cpu_rq (cpu); tg->cfs_rq[cpu] = cfs_rq;init_cfs_rq (cfs_rq, rq); cfs_rq->tg = tg;
kernel/sched.c static void init_tg_cfs_entry(struct rq · line 7174
Quoted 5 lines
kernel/sched.c +1
-1@@ -7170,7 +7171,11 @@ static void init_tg_cfs_entry(struct rqif (!se)return ; - se->cfs_rq = &rq->cfs; +if (parent ==NULL )
!parent ?
Quoted 37 lines
kernel/sched.c +9
-3+ se->cfs_rq = &rq->cfs; + else + se->cfs_rq = parent->my_q; + se->my_q = cfs_rq; se->load.weight = tg->shares; se->load.inv_weight =div64_64 (1ULL <<32 , se->load.weight);@@ -7244,7 +7249,8 @@ void __init sched_init(void)* We achieve this by letting init_task_group's tasks sit * directly in rq->cfs (i.e init_task_group->se[] = NULL). */ -init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_cfs_entry (&init_task_group, &rq->cfs, +NULL , i,1 ,NULL );init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 );#elif definedCONFIG_USER_SCHED /* @@ -7260,7 +7266,7 @@ void __init sched_init(void)*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), - &per_cpu (init_sched_entity, i), i,1 ); + &per_cpu (init_sched_entity, i), i,1 ,NULL );#endif #endif /* CONFIG_FAIR_GROUP_SCHED */ @@ -7630,7 +7636,8 @@ static void free_fair_sched_group(structkfree (tg->se); } -static int alloc_fair_sched_group (struct task_group *tg) +static int alloc_fair_sched_group (struct task_group *tg, +struct task_group *parent) {struct cfs_rq *cfs_rq;struct sched_entity *se;
kernel/sched.c static int alloc_fair_sched_group(struct · line 7672
Quoted 10 lines
kernel/sched.c +5
-2@@ -7658,8 +7665,11 @@ static int alloc_fair_sched_group(struct GFP_KERNEL|__GFP_ZERO, cpu_to_node(i));if (!se) goto err; - -init_tg_cfs_entry (rq, tg, cfs_rq, se, i,0 ); +if (!parent) { +init_tg_cfs_entry (tg, cfs_rq, se, i,0 , parent->se[i]); + }else { +init_tg_cfs_entry (tg, cfs_rq, se, i,0 ,NULL ); + }
Looks like you got the cases switched, this looks like an instant NULL deref.
Quoted 44 lines
kernel/sched.c +5
-8}return 1 ;@@ -7788,7 +7798,7 @@ static void free_sched_group(struct task }/* allocate runqueue etc for a new task group */ -struct task_group *sched_create_group (void ) +struct task_group *sched_create_group (struct task_group *parent) {struct task_group *tg;unsigned long flags;@@ -7798,7 +7808,7 @@ struct task_group *sched_create_group(voif (!tg)return ERR_PTR (-ENOMEM ); -if (!alloc_fair_sched_group (tg)) +if (!alloc_fair_sched_group (tg, parent)) goto err;if (!alloc_rt_sched_group (tg))@@ -8049,7 +8059,7 @@ static inline struct task_group *cgroup_static struct cgroup_subsys_state *cpu_cgroup_create (struct cgroup_subsys *ss,struct cgroup *cgrp) { -struct task_group *tg; +struct task_group *tg, *parent;if (!cgrp->parent) {/* This is early initialization for the top cgroup */ @@ -8057,11 +8067,8 @@ cpu_cgroup_create(struct cgroup_subsys *return &init_task_group.css; } -/* we support only 1-level deep hierarchical scheduler atm */ -if (cgrp->parent->parent) -return ERR_PTR (-EINVAL ); - - tg =sched_create_group (); + parent =cgroup_tg (cgrp->parent); + tg =sched_create_group (parent);if (IS_ERR (tg))return ERR_PTR (-ENOMEM );
Re: [RFC, PATCH 1/2] sched: change the fairness model of the CFS group scheduler
In reply to Dhaval GianiQuoted 3 lines · Dhaval Giani
This patch allows tasks and groups to exist in the same
cfs_rq. With this change the CFS group scheduling follows a 1/(M+N) model from a 1/(1+N) fairness model where M tasks and N groups exist at thecfs_rqlevel.
Good. You know I agree with this direction.
Quoted 52 lines
Signed-off-by Dhaval Giani <[email protected]>Signed-off-by Srivatsa Vaddagiri <[email protected]>--- kernel/sched.c | 46 +++++++++++++++++++++ kernel/sched_fair.c | 113 +++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 137 insertions(+), 22 deletions(-)Index:
linux-2.6.25-rc2/kernel/sched.c
===================================================================kernel/sched.c +19
-0@@ -224,10 +224,13 @@ struct task_group { };#ifdef CONFIG_FAIR_GROUP_SCHED + +#ifdef CONFIG_USER_SCHED /* Default task group's sched entity on each cpu */ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; +#endif static struct sched_entity *init_sched_entity_p[NR_CPUS ];static struct cfs_rq *init_cfs_rq_p[NR_CPUS ];@@ -7163,6 +7166,10 @@ static void init_tg_cfs_entry(struct rqlist_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se; +/* se could be NULL for init_task_group */ +if (!se) +return ; + se->cfs_rq = &rq->cfs; se->my_q = cfs_rq; se->load.weight = tg->shares;@@ -7217,11 +7224,46 @@ void __init sched_init(void)#ifdef CONFIG_FAIR_GROUP_SCHED init_task_group.shares = init_task_group_load;INIT_LIST_HEAD (&rq->leaf_cfs_rq_list); +#ifdef CONFIG_CGROUP_SCHED +/* +* How much cpu bandwidth does init_task_group get? +* +* In case of task-groups formed thr' the cgroup filesystem, it +* gets 100% of the cpu resources in the system. This overall +* system cpu resource is divided among the tasks of +* init_task_group and its child task-groups in a fair manner, +* based on each entity's (task or task-group's) weight +* (se->load.weight). +* +* In other words, if init_task_group has 10 tasks of weight
kernel/sched.c void __init sched_init(void) · line 7248
Quoted 10 lines
kernel/sched.c +10
-0+* 1024) and two child groups A0 and A1 (of weight 1024 each), +* then A0's share of the cpu resource is: +* +* A0's bandwidth = 1024 / (10*1024 + 1024 + 1024) = 8.33% +* +* We achieve this by letting init_task_group's tasks sit +* directly in rq->cfs (i.e init_task_group->se[] = NULL). +*/ +init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 );
That seems to agree with that.
Quoted 5 lines
kernel/sched.c +5
-0+#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed.
kernel/sched.c void __init sched_init(void) · line 7263
Quoted 10 lines
kernel/sched.c +7
-0+* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );
But I fail to parse this lengthy comment. What does it do:
init_group
/ | \
uid-0 uid-1000 uid-n
or does it blend uid-0 into the init_group?
kernel/sched.c static int rebalance_shares(struct sched · line 7482
Quoted 13 lines
kernel/sched.c +4
-0#endif +#endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_RT_GROUP_SCHED init_task_group.rt_runtime = sysctl_sched_rt_runtime *NSEC_PER_USEC ;@@ -7435,6 +7477,10 @@ static int rebalance_shares(struct schedunsigned long total_load =0 , total_shares;struct task_group *tg = cfs_rq->tg; +/* Skip this group if there is no associated group entity */ +if (unlikely (!tg->se[this_cpu])) +continue ;
I'm not directly seeing where tg->se[cpu] == NULL comes from..
Quoted 69 lines
kernel/sched.c +0
-0/* Gather total task load of this group across cpus */ for_each_cpu_mask (i, sdspan) total_load += tg->cfs_rq[i]->load.weight;Index:
linux-2.6.25-rc2/kernel/sched_fair.c
===================================================================kernel/sched_fair.c +37
-0@@ -732,6 +732,21 @@ static inline struct sched_entity *paren return se->parent; } +/* return the cpu load contributed by a given group on a given cpu */ +static inline unsigned long group_cpu_load (struct task_group *tg,int cpu) +{ +struct sched_entity *se = tg->se[cpu], *top_se; +struct cfs_rq *cfs_rq = tg->cfs_rq[cpu]; + +if (unlikely (!se)) +return cfs_rq->load.weight; + +for_each_sched_entity (se) + top_se = se; + +return top_se->load.weight; +} +#define GROUP_IMBALANCE_PCT 20#else /* CONFIG_FAIR_GROUP_SCHED */ @@ -1073,6 +1088,17 @@ out_set_cpu: }#endif /* CONFIG_SMP */ +/* return depth at which a sched entity is present in the hierarchy */ +static inline int depth_se (struct sched_entity *se) +{ +int depth =0 ; + +for_each_sched_entity (se) + depth++; + +return depth; +} +/* * Preempt the current task with a newly woken task if needed: @@ -1083,6 +1109,7 @@ static void check_preempt_wakeup(structstruct cfs_rq *cfs_rq =task_cfs_rq (curr);struct sched_entity *se = &curr->se, *pse = &p->se;unsigned long gran; +int se_depth, pse_depth;if (unlikely (rt_prio (p->prio))) {update_rq_clock (rq);@@ -1100,6 +1127,27 @@ static void check_preempt_wakeup(structif (!sched_feat (WAKEUP_PREEMPT ))return ; +/* +* preemption test can be made between sibling entities who are in the +* same cfs_rq i.e who have a common parent. Walk up the hierarchy of +* both tasks untill we find their ancestors who are siblings of common +* parent. +*/ + +/* First walk up until both entities are at same depth */ + se_depth =depth_se (se); + pse_depth =depth_se (pse);
kernel/sched_fair.c static void check_preempt_wakeup(struct · line 1149
Quoted 10 lines
kernel/sched_fair.c +10
-0+ +while (se_depth > pse_depth) { + se_depth--; + se =parent_entity (se); + } + +while (pse_depth > se_depth) { + pse_depth--; + pse =parent_entity (pse); + }
Sad, but needed.. for now..
Quoted 96 lines
kernel/sched_fair.c +36
-22while (!is_same_group (se, pse)) { se =parent_entity (se); pse =parent_entity (pse);@@ -1166,13 +1214,22 @@ static void put_prev_task_fair(struct rqstatic struct task_struct *__load_balance_iterator (struct cfs_rq *cfs_rq,struct rb_node *curr) { -struct task_struct *p; +struct task_struct *p =NULL ; +struct sched_entity *se;if (!curr)return NULL ; - p = rb_entry(curr, struct task_struct, se.run_node); - cfs_rq->rb_load_balance_curr =rb_next (curr); +/* Skip over entities that are not tasks */ +do { + se = rb_entry(curr, struct sched_entity, run_node); + curr =rb_next (curr); + }while (curr && !entity_is_task (se)); + + cfs_rq->rb_load_balance_curr = curr; + +if (entity_is_task (se)) + p =task_of (se);return p; }@@ -1210,21 +1267,28 @@ load_balance_fair(struct rq *this_rq, instruct cfs_rq *this_cfs_rq = busy_cfs_rq->tg->cfs_rq[this_cpu];unsigned long maxload, task_load, group_weight;unsigned long thisload, per_task_load; -struct sched_entity *se = busy_cfs_rq->tg->se[busiest->cpu]; +struct task_group *tg = busy_cfs_rq->tg; +struct sched_entity *se = tg->se[busiest->cpu], + *this_se = tg->se[this_cpu]; task_load = busy_cfs_rq->load.weight; - group_weight = se->load.weight; +if (!task_load) +continue ; + + group_weight =group_cpu_load (tg, busiest->cpu);/* -* 'group_weight' is contributed by tasks of total weight +* 'group_weight' is contributed by entities of total weight * 'task_load'. To move 'rem_load_move' worth of weight only, * we need to move a maximum task load of: * * maxload = (remload / group_weight) * task_load; */ maxload = (rem_load_move * task_load) / group_weight; +if (!maxload) +continue ; -if (!maxload || !task_load) +if (!busy_cfs_rq->nr_running)continue ; per_task_load = task_load / busy_cfs_rq->nr_running;@@ -1253,23 +1317,28 @@ load_balance_fair(struct rq *this_rq, in &cfs_rq_iterator);#ifdef CONFIG_FAIR_GROUP_SCHED -/* -* load_moved holds the task load that was moved. The -* effective (group) weight moved would be: -* load_moved_eff = load_moved/task_load * group_weight; -*/ - load_moved = (group_weight * load_moved) / task_load; -/* Adjust shares on both cpus to reflect load_moved */ - group_weight -= load_moved; -set_se_shares (se, group_weight); +if (likely (se)) { +unsigned long load_moved_eff; +unsigned long se_shares; - se = busy_cfs_rq->tg->se[this_cpu]; -if (!thisload) - group_weight = load_moved; -else - group_weight = se->load.weight + load_moved; -set_se_shares (se, group_weight); +/* +* load_moved holds the task load that was moved. The +* effective (group) weight moved would be: +* load_moved_eff = load_moved/task_load * +* group_weight; +*/ + load_moved_eff = (se->load.weight * + load_moved) / task_load; + +set_se_shares (se, se->load.weight - load_moved_eff);
kernel/sched_fair.c load_balance_fair(struct rq *this_rq, in · line 1344
Quoted 10 lines
kernel/sched_fair.c +7
-0+if (!thisload) + se_shares = load_moved_eff; +else + se_shares = this_se->load.weight + + load_moved_eff; + set_se_shares(this_se, se_shares); + }#endif rem_load_move -= load_moved;
Didn't pay too much attention to the lb part as you said that needs work.
Re: [RFC, PATCH 1/2] sched: allow the CFS group scheduler to have multiple levels
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
Quoted 1 line · Dhaval Giani
This patch makes the group scheduler multi hierarchy aware.
Ok, good thing to do in principle
thanks!
Quoted 43 lines
Quoted 43 lines
Signed-off-by Dhaval Giani <[email protected]>--- include/linux/sched.h | 2 +- kernel/sched.c | 41 ++++++++++++++++++++++++----------------- 2 files changed, 25 insertions(+), 18 deletions(-)Index:
linux-2.6.25-rc2/include/linux/sched.h
===================================================================include/linux/sched.h +1
-1@@ -2031,7 +2031,7 @@ extern void normalize_rt_tasks(void);extern struct task_group init_task_group; -extern struct task_group *sched_create_group (void ); +extern struct task_group *sched_create_group (struct task_group *parent);extern void sched_destroy_group (struct task_group *tg);extern void sched_move_task (struct task_struct *tsk);#ifdef CONFIG_FAIR_GROUP_SCHED Index:
linux-2.6.25-rc2/kernel/sched.c
===================================================================kernel/sched.c +4
-3@@ -7155,10 +7155,11 @@ static void init_rt_rq(struct rt_rq *rt_ }#ifdef CONFIG_FAIR_GROUP_SCHED -static void init_tg_cfs_entry (struct rq *rq,struct task_group *tg, -struct cfs_rq *cfs_rq,struct sched_entity *se, -int cpu,int add) +static void init_tg_cfs_entry (struct task_group *tg,struct cfs_rq *cfs_rq, +struct sched_entity *se,int cpu,int add, +struct sched_entity *parent) { +struct rq *rq =cpu_rq (cpu); tg->cfs_rq[cpu] = cfs_rq;init_cfs_rq (cfs_rq, rq); cfs_rq->tg = tg;@@ -7170,7 +7171,11 @@ static void init_tg_cfs_entry(struct rqif (!se)return ;
Quoted 5 lines
kernel/sched.c static void init_tg_cfs_entry(struct rq · line 7174
Quoted 2 lines
kernel/sched.c +1
-1- se->cfs_rq = &rq->cfs; +if (parent ==NULL )!parent ?
Will do. (need to start remembering to doing this one!)
Quoted 42 lines
Quoted 42 lines
kernel/sched.c +9
-5+ se->cfs_rq = &rq->cfs; + else + se->cfs_rq = parent->my_q; + se->my_q = cfs_rq; se->load.weight = tg->shares; se->load.inv_weight =div64_64 (1ULL <<32 , se->load.weight);@@ -7244,7 +7249,8 @@ void __init sched_init(void)* We achieve this by letting init_task_group's tasks sit * directly in rq->cfs (i.e init_task_group->se[] = NULL). */ -init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_cfs_entry (&init_task_group, &rq->cfs, +NULL , i,1 ,NULL );init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 );#elif definedCONFIG_USER_SCHED /* @@ -7260,7 +7266,7 @@ void __init sched_init(void)*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), - &per_cpu (init_sched_entity, i), i,1 ); + &per_cpu (init_sched_entity, i), i,1 ,NULL );#endif #endif /* CONFIG_FAIR_GROUP_SCHED */ @@ -7630,7 +7636,8 @@ static void free_fair_sched_group(structkfree (tg->se); } -static int alloc_fair_sched_group (struct task_group *tg) +static int alloc_fair_sched_group (struct task_group *tg, +struct task_group *parent) {struct cfs_rq *cfs_rq;struct sched_entity *se;@@ -7658,8 +7665,11 @@ static int alloc_fair_sched_group(struct GFP_KERNEL|__GFP_ZERO, cpu_to_node(i));if (!se) goto err; - -init_tg_cfs_entry (rq, tg, cfs_rq, se, i,0 );
Quoted 9 lines
kernel/sched.c static int alloc_fair_sched_group(struct · line 7672
Quoted 5 lines
kernel/sched.c +5
-0+if (!parent) { +init_tg_cfs_entry (tg, cfs_rq, se, i,0 , parent->se[i]); + }else { +init_tg_cfs_entry (tg, cfs_rq, se, i,0 ,NULL ); + }Looks like you got the cases switched, this looks like an instant NULL deref.
eeeks! Yeah, you are right. Funny though how I did not hit it while testing.
Signature · 2 lines
regards, Dhaval
Re: [RFC, PATCH 1/2] sched: change the fairness model of the CFS group scheduler
In reply to Peter ZijlstraQuoted 91 lines · Peter Zijlstra
Quoted 3 lines · Dhaval Giani
This patch allows tasks and groups to exist in the same
cfs_rq. With this change the CFS group scheduling follows a 1/(M+N) model from a 1/(1+N) fairness model where M tasks and N groups exist at thecfs_rqlevel.Good. You know I agree with this direction.
Quoted 52 lines
Signed-off-by Dhaval Giani <[email protected]>Signed-off-by Srivatsa Vaddagiri <[email protected]>--- kernel/sched.c | 46 +++++++++++++++++++++ kernel/sched_fair.c | 113 +++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 137 insertions(+), 22 deletions(-)Index:
linux-2.6.25-rc2/kernel/sched.c
===================================================================kernel/sched.c +19
-0@@ -224,10 +224,13 @@ struct task_group { };#ifdef CONFIG_FAIR_GROUP_SCHED + +#ifdef CONFIG_USER_SCHED /* Default task group's sched entity on each cpu */ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; +#endif static struct sched_entity *init_sched_entity_p[NR_CPUS ];static struct cfs_rq *init_cfs_rq_p[NR_CPUS ];@@ -7163,6 +7166,10 @@ static void init_tg_cfs_entry(struct rqlist_add (&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); tg->se[cpu] = se; +/* se could be NULL for init_task_group */ +if (!se) +return ; + se->cfs_rq = &rq->cfs; se->my_q = cfs_rq; se->load.weight = tg->shares;@@ -7217,11 +7224,46 @@ void __init sched_init(void)#ifdef CONFIG_FAIR_GROUP_SCHED init_task_group.shares = init_task_group_load;INIT_LIST_HEAD (&rq->leaf_cfs_rq_list); +#ifdef CONFIG_CGROUP_SCHED +/* +* How much cpu bandwidth does init_task_group get? +* +* In case of task-groups formed thr' the cgroup filesystem, it +* gets 100% of the cpu resources in the system. This overall +* system cpu resource is divided among the tasks of +* init_task_group and its child task-groups in a fair manner, +* based on each entity's (task or task-group's) weight +* (se->load.weight). +* +* In other words, if init_task_group has 10 tasks of weight kernel/sched.c void __init sched_init(void) · line 7248
Quoted 10 lines
kernel/sched.c +10
-0+* 1024) and two child groups A0 and A1 (of weight 1024 each), +* then A0's share of the cpu resource is: +* +* A0's bandwidth = 1024 / (10*1024 + 1024 + 1024) = 8.33% +* +* We achieve this by letting init_task_group's tasks sit +* directly in rq->cfs (i.e init_task_group->se[] = NULL). +*/ +init_tg_cfs_entry (rq, &init_task_group, &rq->cfs,NULL , i,1 ); +init_tg_rt_entry (rq, &init_task_group, &rq->rt,NULL , i,1 );That seems to agree with that.
Quoted 5 lines
kernel/sched.c +5
-0+#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed. kernel/sched.c void __init sched_init(void) · line 7263
Quoted 10 lines
kernel/sched.c +7
-0+* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );But I fail to parse this lengthy comment. What does it do:
Quoted 6 lines
init_group
/ | \
uid-0 uid-1000 uid-nor does it blend uid-0 into the
init_group?
It blends uid-0 (root) into init_group.
<snip>
Quoted 18 lines
Quoted 18 lines
kernel/sched.c +14
-0@@ -1100,6 +1127,27 @@ static void check_preempt_wakeup(structif (!sched_feat (WAKEUP_PREEMPT ))return ; +/* +* preemption test can be made between sibling entities who are in the +* same cfs_rq i.e who have a common parent. Walk up the hierarchy of +* both tasks untill we find their ancestors who are siblings of common +* parent. +*/ + +/* First walk up until both entities are at same depth */ + se_depth =depth_se (se); + pse_depth =depth_se (pse); + +while (se_depth > pse_depth) { + se_depth--; + se =parent_entity (se);
Quoted 9 lines
kernel/sched.c static void check_preempt_wakeup(struct · line 1149
Quoted 6 lines
kernel/sched.c +6
-0+ } + +while (pse_depth > se_depth) { + pse_depth--; + pse =parent_entity (pse); + }Sad, but needed.. for now..
better ideas if any are welcome! Cannot think of anything right now :(
Signature · 2 lines
regards, Dhaval
Re: [RFC, PATCH 1/2] sched: change the fairness model of the CFS group scheduler
Quoted 18 lines · Dhaval Giani
Quoted 18 lines
Quoted 5 lines
kernel/sched.c +5
-0+#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed. kernel/sched.c void __init sched_init(void) · line 7263
Quoted 10 lines
kernel/sched.c +7
-0+* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );But I fail to parse this lengthy comment. What does it do:
Quoted 8 lines
Quoted 6 lines
init_group
/ | \
uid-0 uid-1000 uid-nor does it blend uid-0 into the
init_group?It blends uid-0 (root) into
init_group.
Any particular reason why? It seems to me uid-0 should be treated like any other uid.
Quoted 28 lines
Quoted 18 lines
Quoted 18 lines
kernel/sched_fair.c +14
-0@@ -1100,6 +1127,27 @@ static void check_preempt_wakeup(structif (!sched_feat (WAKEUP_PREEMPT ))return ; +/* +* preemption test can be made between sibling entities who are in the +* same cfs_rq i.e who have a common parent. Walk up the hierarchy of +* both tasks untill we find their ancestors who are siblings of common +* parent. +*/ + +/* First walk up until both entities are at same depth */ + se_depth =depth_se (se); + pse_depth =depth_se (pse); + +while (se_depth > pse_depth) { + se_depth--; + se =parent_entity (se);Quoted 9 lines
kernel/sched_fair.c static void check_preempt_wakeup(struct · line 1149
Quoted 6 lines
kernel/sched_fair.c +6
-0+ } + +while (pse_depth > se_depth) { + pse_depth--; + pse =parent_entity (pse); + }Sad, but needed.. for now..
Quoted 1 line
better ideas if any are welcome! Cannot think of anything right now :(
Single rq can do without :-) If only I could get that latency isolation going...
Re: [RFC, PATCH 1/2] sched: change the fairness model of the CFS group scheduler
Quoted 25 lines · Peter Zijlstra
Quoted 22 lines · Dhaval Giani
Quoted 22 lines
Quoted 5 lines
kernel/sched.c +5
-0+#elif definedCONFIG_USER_SCHED +/* +* In case of task-groups formed thr' the user id of tasks, +* init_task_group represents tasks belonging to root user. +* Hence it forms a sibling of all subsequent groups formed. kernel/sched.c void __init sched_init(void) · line 7263
Quoted 10 lines
kernel/sched.c +7
-0+* In this case, init_task_group gets only a fraction of overall +* system cpu resource, based on the weight assigned to root +* user's cpu share (INIT_TASK_GROUP_LOAD). This is accomplished +* by letting tasks of init_task_group sit in a separate cfs_rq +* (init_cfs_rq) and having one entity represent this group of +* tasks in rq->cfs (i.e init_task_group->se[] != NULL). +*/ init_tg_cfs_entry (rq, &init_task_group, &per_cpu (init_cfs_rq, i), &per_cpu (init_sched_entity, i), i,1 );But I fail to parse this lengthy comment. What does it do:
init_group
/ | \
uid-0 uid-1000 uid-n
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
or does it blend uid-0 into the
init_group?It blends uid-0 (root) into
init_group.Any particular reason why? It seems to me uid-0 should be treated like any other uid.
Ah, I misunderstood your question. We have not changed anything for UID scheduling as no task can (should) exist at the root level (init_group). Your initial figure is right, sorry for the confusion.
Thanks,
Signature · 2 lines
regards, Dhaval