sched: Implement on-demand (active) cfs_rq list

Make certain load-balance actions scale per number of active cgroups
instead of the number of existing cgroups.

This makes wakeup/sleep paths more expensive, but is a win for systems
where the vast majority of existing cgroups are idle.

Signed-off-by: Paul Turner <pjt@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <20101115234937.666535048@google.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>

3 files changed, 92 insertions, 83 deletions

diff --git a/kernel/sched.c b/kernel/sched.c
index e2f1a3024a99..22436dd2e19f 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -274,9 +274,7 @@ struct task_group {
 
 #define root_task_group init_task_group
 
-/* task_group_lock serializes add/remove of task groups and also changes to
- * a task group's cpu shares.
- */
+/* task_group_lock serializes the addition/removal of task groups */
 static DEFINE_SPINLOCK(task_group_lock);
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
@@ -344,6 +342,7 @@ struct cfs_rq {
          * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
          * list is used during load balance.
          */
+        int on_list;
         struct list_head leaf_cfs_rq_list;
         struct task_group *tg;  /* group that "owns" this runqueue */
 
@@ -1547,7 +1546,7 @@ static unsigned long cpu_avg_load_per_task(int cpu)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
-static void update_cfs_load(struct cfs_rq *cfs_rq);
+static void update_cfs_load(struct cfs_rq *cfs_rq, int lb);
 static void update_cfs_shares(struct cfs_rq *cfs_rq);
 
 /*
@@ -1570,7 +1569,7 @@ static int tg_shares_up(struct task_group *tg, void *data)
         raw_spin_lock_irqsave(&rq->lock, flags);
 
         update_rq_clock(rq);
-        update_cfs_load(cfs_rq);
+        update_cfs_load(cfs_rq, 1);
 
         load_avg = div64_u64(cfs_rq->load_avg, cfs_rq->load_period+1);
         load_avg -= cfs_rq->load_contribution;
@@ -7688,15 +7687,13 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
-                                struct sched_entity *se, int cpu, int add,
+                                struct sched_entity *se, int cpu,
                                 struct sched_entity *parent)
 {
         struct rq *rq = cpu_rq(cpu);
         tg->cfs_rq[cpu] = cfs_rq;
         init_cfs_rq(cfs_rq, rq);
         cfs_rq->tg = tg;
-        if (add)
-                list_add(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
 
         tg->se[cpu] = se;
         /* se could be NULL for init_task_group */
@@ -7716,7 +7713,7 @@ static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
 
 #ifdef CONFIG_RT_GROUP_SCHED
 static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
-                struct sched_rt_entity *rt_se, int cpu, int add,
+                struct sched_rt_entity *rt_se, int cpu,
                 struct sched_rt_entity *parent)
 {
         struct rq *rq = cpu_rq(cpu);
@@ -7725,8 +7722,6 @@ static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
         init_rt_rq(rt_rq, rq);
         rt_rq->tg = tg;
         rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
-        if (add)
-                list_add(&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list);
 
         tg->rt_se[cpu] = rt_se;
         if (!rt_se)
@@ -7835,7 +7830,7 @@ void __init sched_init(void)
                  * We achieve this by letting init_task_group's tasks sit
                  * directly in rq->cfs (i.e init_task_group->se[] = NULL).
                  */
-                init_tg_cfs_entry(&init_task_group, &rq->cfs, NULL, i, 1, NULL);
+                init_tg_cfs_entry(&init_task_group, &rq->cfs, NULL, i, NULL);
 #endif
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
@@ -7843,7 +7838,7 @@ void __init sched_init(void)
 #ifdef CONFIG_RT_GROUP_SCHED
                 INIT_LIST_HEAD(&rq->leaf_rt_rq_list);
 #ifdef CONFIG_CGROUP_SCHED
-                init_tg_rt_entry(&init_task_group, &rq->rt, NULL, i, 1, NULL);
+                init_tg_rt_entry(&init_task_group, &rq->rt, NULL, i, NULL);
 #endif
 #endif
 
@@ -8119,7 +8114,7 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
                 if (!se)
                         goto err_free_rq;
 
-                init_tg_cfs_entry(tg, cfs_rq, se, i, 0, parent->se[i]);
+                init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
         }
 
         return 1;
@@ -8130,15 +8125,22 @@ err:
         return 0;
 }
 
-static inline void register_fair_sched_group(struct task_group *tg, int cpu)
-{
-        list_add_rcu(&tg->cfs_rq[cpu]->leaf_cfs_rq_list,
-                        &cpu_rq(cpu)->leaf_cfs_rq_list);
-}
-
 static inline void unregister_fair_sched_group(struct task_group *tg, int cpu)
 {
-        list_del_rcu(&tg->cfs_rq[cpu]->leaf_cfs_rq_list);
+        struct rq *rq = cpu_rq(cpu);
+        unsigned long flags;
+        int i;
+
+        /*
+        * Only empty task groups can be destroyed; so we can speculatively
+        * check on_list without danger of it being re-added.
+        */
+        if (!tg->cfs_rq[cpu]->on_list)
+                return;
+
+        raw_spin_lock_irqsave(&rq->lock, flags);
+        list_del_leaf_cfs_rq(tg->cfs_rq[i]);
+        raw_spin_unlock_irqrestore(&rq->lock, flags);
 }
 #else /* !CONFG_FAIR_GROUP_SCHED */
 static inline void free_fair_sched_group(struct task_group *tg)
@@ -8151,10 +8153,6 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
         return 1;
 }
 
-static inline void register_fair_sched_group(struct task_group *tg, int cpu)
-{
-}
-
 static inline void unregister_fair_sched_group(struct task_group *tg, int cpu)
 {
 }
@@ -8209,7 +8207,7 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
                 if (!rt_se)
                         goto err_free_rq;
 
-                init_tg_rt_entry(tg, rt_rq, rt_se, i, 0, parent->rt_se[i]);
+                init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]);
         }
 
         return 1;
@@ -8219,17 +8217,6 @@ err_free_rq:
 err:
         return 0;
 }
-
-static inline void register_rt_sched_group(struct task_group *tg, int cpu)
-{
-        list_add_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list,
-                        &cpu_rq(cpu)->leaf_rt_rq_list);
-}
-
-static inline void unregister_rt_sched_group(struct task_group *tg, int cpu)
-{
-        list_del_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list);
-}