Skip to contentSkip to conversation

sched/fair: Use task_groups instead of leaf_cfs_rq_list to walk all cfs_rqs

PATCH In review Tejun Heo 3 participants 12 messages May 9, 2017 – May 27, 2017 Scheduler

lore
Share & tools
lore

Tejun Heo

author
#0 lore raw

PATCH v2 1/2 sched/fair: Use task_groups instead of leaf_cfs_rq_list to walk all cfs_rqs

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(total number of CPU cgroups) which isn't scalable at all.

The next patch will make rq->leaf_cfs_rq_list only contain the cfs_rqs which are currently active. In preparation, this patch converts users which need to traverse all cfs_rqs to use task_groups list instead.

task_groups list is protected by its own lock and allows RCU protected traversal and the order of operations guarantees that all online cfs_rqs will be visited, but holding rq->lock won't protect against iterating an already unregistered cfs_rq. However, the operations of the two users that get converted - update_runtime_enabled() and unthrottle_offline_cfs_rqs() - should be safe to perform on already dead cfs_rqs, so adding rcu read protection around them should be enough.

Note that print_cfs_stats() is not converted. The next patch will change its behavior to print out only active cfs_rqs, which is intended as there's not much point in printing out idle cfs_rqs.

v2: Dropped strong synchronization around removal and left
print_cfs_stats() unchanged as suggested by Peterz.

Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>

---
Peter,

Updated the patch - pasted in your version and updated the description accordingly. Please feel free to use this one or whichever you like.

Based on mainline and stable is cc'd.

Thanks.

 kernel/sched/fair.c |   21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)
kernel/sched/fair.c +16 -5
@@ -4644,22 +4644,32 @@ static void destroy_cfs_bandwidth(struct
 
 static void __maybe_unused update_runtime_enabled(struct rq *rq)
 {
-	struct cfs_rq *cfs_rq;
+	struct task_group *tg;
 
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		struct cfs_bandwidth *cfs_b = &cfs_rq->tg->cfs_bandwidth;
+	lockdep_assert_held(&rq->lock);
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(tg, &task_groups, list) {
+		struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;
+		struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
 
 		raw_spin_lock(&cfs_b->lock);
 		cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF;
 		raw_spin_unlock(&cfs_b->lock);
 	}
+	rcu_read_unlock();
 }
 
 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
 {
-	struct cfs_rq *cfs_rq;
+	struct task_group *tg;
+
+	lockdep_assert_held(&rq->lock);
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(tg, &task_groups, list) {
+		struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
 
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		if (!cfs_rq->runtime_enabled)
 			continue;
 
@@ -4677,6 +4687,7 @@ static void __maybe_unused unthrottle_of
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
 	}
+	rcu_read_unlock();
 }
 
 #else /* CONFIG_CFS_BANDWIDTH */
author
#1 lore raw

PATCH v2 2/2 sched/fair: Fix O(# total cgroups) in load balance path

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

This shows up as a small CPU consumption and scheduling latency increase in the load balancing path in systems with CPU controller enabled across most cgroups. In an edge case where temporary cgroups were leaking, this caused the kernel to consume good several tens of percents of CPU cycles running update_blocked_averages(), each run taking multiple millisecs.

This patch fixes the issue by taking empty and fully decayed cfs_rqs off the rq->leaf_cfs_rq_list.

Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>

---
Just refreshed on top of the first patch.

 kernel/sched/fair.c |   19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +14 -5
@@ -369,8 +369,9 @@ static inline void list_del_leaf_cfs_rq(
 }
 
 /* Iterate thr' all leaf cfs_rq's on a runqueue */
-#define for_each_leaf_cfs_rq(rq, cfs_rq) \
-	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)			\
+	list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list,	\
+				 leaf_cfs_rq_list)
 
 /* Do the two (enqueued) entities belong to the same group ? */
 static inline struct cfs_rq *
@@ -463,7 +464,7 @@ static inline void list_del_leaf_cfs_rq(
 {
 }
 
-#define for_each_leaf_cfs_rq(rq, cfs_rq) \
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)	\
 		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
 
 static inline struct sched_entity *parent_entity(struct sched_entity *se)
@@ -6984,7 +6985,7 @@ static void attach_tasks(struct lb_env *
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	struct cfs_rq *cfs_rq;
+	struct cfs_rq *cfs_rq, *pos;
 	struct rq_flags rf;
 
 	rq_lock_irqsave(rq, &rf);
@@ -6994,7 +6995,7 @@ static void update_blocked_averages(int
 	 * Iterates the task_group tree in a bottom up fashion, see
 	 * list_add_leaf_cfs_rq() for details.
 	 */
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
+	for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) {
 		struct sched_entity *se;
 
 		/* throttled entities do not contribute to load */
@@ -7008,6 +7009,14 @@ static void update_blocked_averages(int
 		se = cfs_rq->tg->se[cpu];
 		if (se && !skip_blocked_update(se))
 			update_load_avg(se, 0);
+
+		/*
+		 * There can be a lot of idle CPU cgroups.  Don't let fully
+		 * decayed cfs_rqs linger on the list.
+		 */
+		if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+		    !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+			list_del_leaf_cfs_rq(cfs_rq);
 	}
 	rq_unlock_irqrestore(rq, &rf);
 }
maintainer
#2 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

Hi Tejun,

Quoted 4 lines · Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

Dietmar raised similar optimization in the past. The only question was : what is the impact of re-adding the cfs_rq in leaf_cfs_rq_list on the wake up path ? Have you done some measurements ?

Quoted 67 lines

This shows up as a small CPU consumption and scheduling latency increase in the load balancing path in systems with CPU controller enabled across most cgroups. In an edge case where temporary cgroups were leaking, this caused the kernel to consume good several tens of percents of CPU cycles running update_blocked_averages(), each run taking multiple millisecs.

This patch fixes the issue by taking empty and fully decayed cfs_rqs off the rq->leaf_cfs_rq_list.

Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>

---
Just refreshed on top of the first patch.

 kernel/sched/fair.c |   19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)
kernel/sched/fair.c +6 -5
@@ -369,8 +369,9 @@ static inline void list_del_leaf_cfs_rq(
 }
 
 /* Iterate thr' all leaf cfs_rq's on a runqueue */
-#define for_each_leaf_cfs_rq(rq, cfs_rq) \
-       list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)                     \
+       list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list,    \
+                                leaf_cfs_rq_list)
 
 /* Do the two (enqueued) entities belong to the same group ? */
 static inline struct cfs_rq *
@@ -463,7 +464,7 @@ static inline void list_del_leaf_cfs_rq(
 {
 }
 
-#define for_each_leaf_cfs_rq(rq, cfs_rq) \
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos)     \
                for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
 
 static inline struct sched_entity *parent_entity(struct sched_entity *se)
@@ -6984,7 +6985,7 @@ static void attach_tasks(struct lb_env *
 static void update_blocked_averages(int cpu)
 {
        struct rq *rq = cpu_rq(cpu);
-       struct cfs_rq *cfs_rq;
+       struct cfs_rq *cfs_rq, *pos;
        struct rq_flags rf;
 
        rq_lock_irqsave(rq, &rf);
@@ -6994,7 +6995,7 @@ static void update_blocked_averages(int
         * Iterates the task_group tree in a bottom up fashion, see
         * list_add_leaf_cfs_rq() for details.
         */
-       for_each_leaf_cfs_rq(rq, cfs_rq) {
+       for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) {
                struct sched_entity *se;
 
                /* throttled entities do not contribute to load */
@@ -7008,6 +7009,14 @@ static void update_blocked_averages(int
                se = cfs_rq->tg->se[cpu];

kernel/sched/fair.c static void update_blocked_averages(int · line 7019

Quoted 10 lines
kernel/sched/fair.c +8 -0
                if (se && !skip_blocked_update(se))
                        update_load_avg(se, 0);
+
+               /*
+                * There can be a lot of idle CPU cgroups.  Don't let fully
+                * decayed cfs_rqs linger on the list.
+                */
+               if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+                   !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+                       list_del_leaf_cfs_rq(cfs_rq);

list_add_leaf_cfs_rq() assumes that we always enqueue cfs_rq bottom-up. By removing cfs_rq, can't we break this assumption in some cases ?

Regards,
Vincent

Quoted 3 lines
kernel/sched/fair.c +0 -0
        }
        rq_unlock_irqrestore(rq, &rf);
 }
author
#3 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

Hello,

Quoted 9 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

Dietmar raised similar optimization in the past. The only question was : what is the impact of re-adding the cfs_rq in leaf_cfs_rq_list on the wake up path ? Have you done some measurements ?

Didn't do a perf test yet but it's several more branches and a local list operation on enqueue, which is already pretty expensive vs. load balance being O(total number of cgroups on the system).

Anyways, I'll do some hackbench tests with several levels of layering.

Quoted 7 lines
Quoted 7 lines
kernel/sched/fair.c +3 -0
@@ -7008,6 +7009,14 @@ static void update_blocked_averages(int
                se = cfs_rq->tg->se[cpu];
                if (se && !skip_blocked_update(se))
                        update_load_avg(se, 0);
+
+               /*
+                * There can be a lot of idle CPU cgroups.  Don't let fully
Quoted 8 lines

kernel/sched/fair.c static void update_blocked_averages(int · line 7019

Quoted 5 lines
kernel/sched/fair.c +5 -0
+                * decayed cfs_rqs linger on the list.
+                */
+               if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+                   !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+                       list_del_leaf_cfs_rq(cfs_rq);

list_add_leaf_cfs_rq() assumes that we always enqueue cfs_rq bottom-up. By removing cfs_rq, can't we break this assumption in some cases ?

We queue a cfs_rq on the leaf list when the a se is queued on that cfs_rq for the first time, so queueing can happen in any order; otherwise, we'd simply be doing list_add_tail(). AFAICS, removing and re-adding shouldn't break anything if the code wasn't broken before.

Thanks.

Signature · 1 line
tejun
author
#4 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

Quoted 13 lines · Tejun Heo

Hello,

Quoted 9 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

Dietmar raised similar optimization in the past. The only question was : what is the impact of re-adding the cfs_rq in leaf_cfs_rq_list on the wake up path ? Have you done some measurements ?

Quoted 5 lines

Didn't do a perf test yet but it's several more branches and a local list operation on enqueue, which is already pretty expensive vs. load balance being O(total number of cgroups on the system).

Anyways, I'll do some hackbench tests with several levels of layering.

Oh, BTW, do we still need bc4278987e38 ("sched/fair: Fix FTQ noise bench regression") with this patch? That patch looks like it's just cutting down on the body of the O(#cgroups) loop.

Ying, can you verify whether the following patch on top of the current linus#master 56868a460b83 also fixes the regression that you saw?

kernel/sched/fair.c +36 -43
Index: work/kernel/sched/fair.c
===================================================================
@@ -372,6 +372,10 @@ static inline void list_del_leaf_cfs_rq(
 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
 	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
 
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \
+	list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list, \
+				 leaf_cfs_rq_list)
+
 /* Do the two (enqueued) entities belong to the same group ? */
 static inline struct cfs_rq *
 is_same_group(struct sched_entity *se, struct sched_entity *pse)
@@ -466,6 +470,9 @@ static inline void list_del_leaf_cfs_rq(
 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
 		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
 
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \
+		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
+
 static inline struct sched_entity *parent_entity(struct sched_entity *se)
 {
 	return NULL;
@@ -3170,36 +3177,6 @@ static inline int propagate_entity_load_
 	return 1;
 }
 
-/*
- * Check if we need to update the load and the utilization of a blocked
- * group_entity:
- */
-static inline bool skip_blocked_update(struct sched_entity *se)
-{
-	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-
-	/*
-	 * If sched_entity still have not zero load or utilization, we have to
-	 * decay it:
-	 */
-	if (se->avg.load_avg || se->avg.util_avg)
-		return false;
-
-	/*
-	 * If there is a pending propagation, we have to update the load and
-	 * the utilization of the sched_entity:
-	 */
-	if (gcfs_rq->propagate_avg)
-		return false;
-
-	/*
-	 * Otherwise, the load and the utilization of the sched_entity is
-	 * already zero and there is no pending propagation, so it will be a
-	 * waste of time to try to decay it:
-	 */
-	return true;
-}
-
 #else /* CONFIG_FAIR_GROUP_SCHED */
 
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force) {}
@@ -4644,22 +4621,32 @@ static void destroy_cfs_bandwidth(struct
 
 static void __maybe_unused update_runtime_enabled(struct rq *rq)
 {
-	struct cfs_rq *cfs_rq;
+	struct task_group *tg;
+
+	lockdep_assert_held(&rq->lock);
 
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		struct cfs_bandwidth *cfs_b = &cfs_rq->tg->cfs_bandwidth;
+	rcu_read_lock();
+	list_for_each_entry_rcu(tg, &task_groups, list) {
+		struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;
+		struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
 
 		raw_spin_lock(&cfs_b->lock);
 		cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF;
 		raw_spin_unlock(&cfs_b->lock);
 	}
+	rcu_read_unlock();
 }
 
 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
 {
-	struct cfs_rq *cfs_rq;
+	struct task_group *tg;
+
+	lockdep_assert_held(&rq->lock);
+
+	rcu_read_lock();
+	list_for_each_entry_rcu(tg, &task_groups, list) {
+		struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
 
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
 		if (!cfs_rq->runtime_enabled)
 			continue;
 
@@ -4677,6 +4664,7 @@ static void __maybe_unused unthrottle_of
 		if (cfs_rq_throttled(cfs_rq))
 			unthrottle_cfs_rq(cfs_rq);
 	}
+	rcu_read_unlock();
 }
 
 #else /* CONFIG_CFS_BANDWIDTH */
@@ -6973,7 +6961,7 @@ static void attach_tasks(struct lb_env *
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	struct cfs_rq *cfs_rq;
+	struct cfs_rq *cfs_rq, *pos;
 	struct rq_flags rf;
 
 	rq_lock_irqsave(rq, &rf);
@@ -6983,9 +6971,7 @@ static void update_blocked_averages(int
 	 * Iterates the task_group tree in a bottom up fashion, see
 	 * list_add_leaf_cfs_rq() for details.
 	 */
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
-		struct sched_entity *se;
-
+	for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) {
 		/* throttled entities do not contribute to load */
 		if (throttled_hierarchy(cfs_rq))
 			continue;
@@ -6993,10 +6979,17 @@ static void update_blocked_averages(int
 		if (update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq, true))
 			update_tg_load_avg(cfs_rq, 0);
 
-		/* Propagate pending load changes to the parent, if any: */
-		se = cfs_rq->tg->se[cpu];
-		if (se && !skip_blocked_update(se))
-			update_load_avg(se, 0);
+		/* Propagate pending load changes to the parent */
+		if (cfs_rq->tg->se[cpu])
+			update_load_avg(cfs_rq->tg->se[cpu], 0);
+
+		/*
+		 * There can be a lot of idle CPU cgroups.  Don't let fully
+		 * decayed cfs_rqs linger on the list.
+		 */
+		if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+		    !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+			list_del_leaf_cfs_rq(cfs_rq);
 	}
 	rq_unlock_irqrestore(rq, &rf);
 }
maintainer
#5 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

In reply to Tejun Heo

Hi Tejun,

Quoted 35 lines · Tejun Heo

Hello,

Quoted 9 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

Dietmar raised similar optimization in the past. The only question was : what is the impact of re-adding the cfs_rq in leaf_cfs_rq_list on the wake up path ? Have you done some measurements ?

Didn't do a perf test yet but it's several more branches and a local list operation on enqueue, which is already pretty expensive vs. load balance being O(total number of cgroups on the system).

Anyways, I'll do some hackbench tests with several levels of layering.

Quoted 7 lines
Quoted 7 lines
kernel/sched/fair.c +3 -0
@@ -7008,6 +7009,14 @@ static void update_blocked_averages(int
                se = cfs_rq->tg->se[cpu];
                if (se && !skip_blocked_update(se))
                        update_load_avg(se, 0);
+
+               /*
+                * There can be a lot of idle CPU cgroups.  Don't let fully
Quoted 8 lines

kernel/sched/fair.c static void update_blocked_averages(int · line 7019

Quoted 5 lines
kernel/sched/fair.c +5 -0
+                * decayed cfs_rqs linger on the list.
+                */
+               if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+                   !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+                       list_del_leaf_cfs_rq(cfs_rq);

list_add_leaf_cfs_rq() assumes that we always enqueue cfs_rq bottom-up. By removing cfs_rq, can't we break this assumption in some cases ?

Quoted 2 lines

We queue a cfs_rq on the leaf list when the a se is queued on that cfs_rq for the first time, so queueing can happen in any order;

Sorry, what i mean is:
When the group entity of a cfs_rq is enqueued, we are sure that either the parents is already enqueued or it will be enqueued in the same sequence. We must be sure that no other branch will be enqueued in the middle of the sequence and will reset tmp_alone_branch. This is true with current implementation but I wondered it can happen if we del/add the cfs_rq out of order

That said i haven't find a use case that break the sequence

Quoted 7 lines

otherwise, we'd simply be doing list_add_tail(). AFAICS, removing and re-adding shouldn't break anything if the code wasn't broken before.

Thanks.

--
tejun

author
#6 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

Hello, Vincent.

Quoted 9 lines · Vincent Guittot

Sorry, what i mean is:
When the group entity of a cfs_rq is enqueued, we are sure that either the parents is already enqueued or it will be enqueued in the same sequence. We must be sure that no other branch will be enqueued in the middle of the sequence and will reset tmp_alone_branch. This is true with current implementation but I wondered it can happen if we del/add the cfs_rq out of order

That said i haven't find a use case that break the sequence

Hmm... a cfs_rq can be removed from leaf list iff it's empty and dequeued, and enqueueing is always from top down. If an ancestor is already enqueued, it's guaranteed to be on the leaf list; otherwise, it's guaranteed to be enqueued beforehand and thus put on the leaf list too. I think it should be fine.

Thanks.

Signature · 1 line
tejun
maintainer Acked-by
#7 lore raw

Re: [PATCH v2 for-4.12-fixes 2/2] sched/fair: Fix O(# total cgroups) in load balance path

Quoted 11 lines · Tejun Heo

Hello, Vincent.

Quoted 8 lines · Vincent Guittot

Sorry, what i mean is:
When the group entity of a cfs_rq is enqueued, we are sure that either the parents is already enqueued or it will be enqueued in the same sequence. We must be sure that no other branch will be enqueued in the middle of the sequence and will reset tmp_alone_branch. This is true with current implementation but I wondered it can happen if we del/add the cfs_rq out of order

Quoted 7 lines
Quoted 1 line

That said i haven't find a use case that break the sequence

Hmm... a cfs_rq can be removed from leaf list iff it's empty and dequeued, and enqueueing is always from top down. If an ancestor is already enqueued, it's guaranteed to be on the leaf list; otherwise, it's guaranteed to be enqueued beforehand and thus put on the leaf list too. I think it should be fine.

I agree

FWIW

Quoted 5 lines

Thanks.

--
tejun

author
#8 lore raw

PATCH v3 2/2 sched/fair: Fix O(# total cgroups) in load balance path

In reply to Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(# total cgroups) which isn't scalable at all.

This shows up as a small CPU consumption and scheduling latency increase in the load balancing path in systems with CPU controller enabled across most cgroups. In an edge case where temporary cgroups were leaking, this caused the kernel to consume good several tens of percents of CPU cycles running update_blocked_averages(), each run taking multiple millisecs.

This patch fixes the issue by taking empty and fully decayed cfs_rqs off the rq->leaf_cfs_rq_list.

v3: The debug path still uses for_each_leaf_cfs_rq(). Keep it around.

Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>

---
Hello,

The previous patch caused build error if SCHED_DEBUG is set as that still uses for_each_leaf_cfs_rq(). Patch updated to keep that around.

Thanks.

 kernel/sched/fair.c |   19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)
kernel/sched/fair.c +17 -2
@@ -372,6 +372,10 @@ static inline void list_del_leaf_cfs_rq(
 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
 	list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
 
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \
+	list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list, \
+				 leaf_cfs_rq_list)
+
 /* Do the two (enqueued) entities belong to the same group ? */
 static inline struct cfs_rq *
 is_same_group(struct sched_entity *se, struct sched_entity *pse)
@@ -466,6 +470,9 @@ static inline void list_del_leaf_cfs_rq(
 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
 		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
 
+#define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \
+		for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
+
 static inline struct sched_entity *parent_entity(struct sched_entity *se)
 {
 	return NULL;
@@ -6984,7 +6991,7 @@ static void attach_tasks(struct lb_env *
 static void update_blocked_averages(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
-	struct cfs_rq *cfs_rq;
+	struct cfs_rq *cfs_rq, *pos;
 	struct rq_flags rf;
 
 	rq_lock_irqsave(rq, &rf);
@@ -6994,7 +7001,7 @@ static void update_blocked_averages(int
 	 * Iterates the task_group tree in a bottom up fashion, see
 	 * list_add_leaf_cfs_rq() for details.
 	 */
-	for_each_leaf_cfs_rq(rq, cfs_rq) {
+	for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) {
 		struct sched_entity *se;
 
 		/* throttled entities do not contribute to load */
@@ -7008,6 +7015,14 @@ static void update_blocked_averages(int
 		se = cfs_rq->tg->se[cpu];
 		if (se && !skip_blocked_update(se))
 			update_load_avg(se, 0);
+
+		/*
+		 * There can be a lot of idle CPU cgroups.  Don't let fully
+		 * decayed cfs_rqs linger on the list.
+		 */
+		if (!cfs_rq->load.weight && !cfs_rq->avg.load_sum &&
+		    !cfs_rq->avg.util_sum && !cfs_rq->runnable_load_sum)
+			list_del_leaf_cfs_rq(cfs_rq);
 	}
 	rq_unlock_irqrestore(rq, &rf);
 }
#9 lore raw
In reply to Tejun Heo
Quoted 18 lines · Tejun Heo

Currently, rq->leaf_cfs_rq_list is a traversal ordered list of all live cfs_rqs which have ever been active on the CPU; unfortunately, this makes update_blocked_averages() O(total number of CPU cgroups) which isn't scalable at all.

The next patch will make rq->leaf_cfs_rq_list only contain the cfs_rqs which are currently active. In preparation, this patch converts users which need to traverse all cfs_rqs to use task_groups list instead.

task_groups list is protected by its own lock and allows RCU protected traversal and the order of operations guarantees that all online cfs_rqs will be visited, but holding rq->lock won't protect against iterating an already unregistered cfs_rq. However, the operations of the two users that get converted - update_runtime_enabled() and unthrottle_offline_cfs_rqs() - should be safe to perform on already dead cfs_rqs, so adding rcu read protection around them should be enough.

Quoted 8 lines

Note that print_cfs_stats() is not converted. The next patch will change its behavior to print out only active cfs_rqs, which is intended as there's not much point in printing out idle cfs_rqs.

v2: Dropped strong synchronization around removal and left
print_cfs_stats() unchanged as suggested by Peterz.

Tejun,

We did some preliminary testing of this patchset for a well known database benchmark on a 4 socket Skylake server system. It provides a 3.7% throughput boost which is significant for this benchmark.

Thanks.

Tim

author
#10 lore raw
Quoted 4 lines · Tim Chen

We did some preliminary testing of this patchset for a well known database benchmark on a 4 socket Skylake server system. It provides a 3.7% throughput boost which is significant for this benchmark.

That's great to hear. Yeah, the walk can be noticeably expensive even with moderate number of cgroups. Thanks for sharing the result.

Signature · 1 line
tejun
#11 lore raw
Quoted 9 lines · Tejun Heo
Quoted 4 lines · Tim Chen

We did some preliminary testing of this patchset for a well known database benchmark on a 4 socket Skylake server system. It provides a 3.7% throughput boost which is significant for this benchmark.

That's great to hear. Yeah, the walk can be noticeably expensive even with moderate number of cgroups. Thanks for sharing the result.

Yes, the walk in update_blocked_averages has bad scaling property as it iterates over *all* cfs_rq's leaf tasks, making it very expensive. It consumes 11.7% of our cpu cycles for this benchmark when CGROUP is on. Your patchset skips unused cgroup and reduce the overhead to 10.4%. CPU cycles profile is attached below for your reference.

The scheduler's frequent update of cgroup's laod averages, and having to iterate all the leaf tasks for each load balance causes update_blocked_averages to be one of the most expensive functions in the system, making CGROUP costly. Without CGROUP, schedule only cost 3.3% of cpu cycles vs 16.4% with CGROUP turned on. Your patchset does reduce it to 14.9%.

This benchmark has thousands of running tasks, so it puts a good deal of stress to the scheduler.

Tim

CPU cycles profile:

4.11 Before your patchset with CGROUP:
---------------------------------------

    16.42%     0.03%           280  [kernel.vmlinux]                                [k] schedule
            |
             --16.39%--schedule
                       |
                        --16.31%--__sched_text_start
                                  |
                                  |--12.85%--pick_next_task_fair
                                  |          |
                                  |           --11.71%--update_blocked_averages
                                  |                     |
                                  |                      --5.00%--update_load_avg
                                  |
                                  |--2.04%--finish_task_switch
                                  |          |
                                  |          |--0.85%--ret_from_intr
                                  |          |          |
                                  |          |           --0.85%--do_IRQ
                                  |          |
                                  |           --0.75%--apic_timer_interrupt
                                  |                     |
                                  |                      --0.75%--smp_apic_timer_interrupt
                                  |                                |
                                  |                                 --0.55%--irq_exit
                                  |                                           |
                                  |                                            --0.55%--__do_softirq
                                  |
                                   --0.51%--deactivate_task

4.11 After your patchset with CGROUP:
-------------------------------------

    14.90%     0.04%           337  [kernel.vmlinux]                                [k] schedule
            |
             --14.86%--schedule
                       |
                        --14.78%--__sched_text_start
                                  |
                                  |--11.51%--pick_next_task_fair
                                  |          |
                                  |           --10.37%--update_blocked_averages
                                  |                     |
                                  |                      --4.55%--update_load_avg
                                  |
                                  |--1.79%--finish_task_switch
                                  |          |
                                  |          |--0.77%--ret_from_intr
                                  |          |          |
                                  |          |           --0.77%--do_IRQ
                                  |          |
                                  |           --0.65%--apic_timer_interrupt
                                  |                     |
                                  |                      --0.65%--smp_apic_timer_interrupt
                                  |
                                   --0.53%--deactivate_task

4.11 with No CGROUP:
--------------------

     3.33%     0.04%           336  [kernel.vmlinux]                                [k] schedule
            |
             --3.29%--schedule
                       |
                        --3.19%--__sched_text_start
                                  |
                                   --1.45%--pick_next_task_fair
                                             |
                                              --1.15%--load_balance
                                                        |
                                                         --0.87%--find_busiest_group
                                                                   |
                                                                    --0.82%--update_sd_lb_stats