Skip to contentSkip to conversation

sched,cfs: flatten CPU controller runqueues

RFC Superseded Rik van Riel 2 participants 24 messages Jun 12, 2019 – Jun 28, 2019 Scheduler

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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(-)
#1 lore raw

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
index f35930f5e528..df624f7a68e7 100644
@@ -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
#2 lore raw

Re: [PATCH 1/8] sched: introduce task_se_h_load helper

Quoted 28 lines · Rik van Riel

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 +1 -1
index f35930f5e528..df624f7a68e7 100644
@@ -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?

[...]

#3 lore raw

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.
#4 lore raw

Re: [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_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.

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 ...

#5 lore raw

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_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.

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.

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.
#6 lore raw

PATCH 2/8 sched: change /proc/sched_debug fields

In reply to Rik van Riel

Remove 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
index 678bfb9bd87f..aab4640d66c5 100644
@@ -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
#7 lore raw

PATCH 3/8 sched,fair: redefine runnable_load_avg as the sum of task_h_load

In reply to Rik van Riel

The 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
index 11837410690f..f5bb6948e40c 100644
@@ -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
index 874c427742a9..fbd96900f715 100644
@@ -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
index aab4640d66c5..d06e7436d148 100644
@@ -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
index b52ed1ada0be..5be14cee61f9 100644
@@ -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
#8 lore raw

Re: [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).

[...]

#9 lore raw

Re: [PATCH 3/8] sched,fair: redefine runnable_load_avg as the sum of task_h_load

In reply to Rik van Riel
Quoted 2 lines · Rik van Riel

The runnable_load magic 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_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 +0 -0
index 11837410690f..f5bb6948e40c 100644

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).

[...]

#10 lore raw

PATCH 4/8 sched,fair: remove cfs rqs from leaf_cfs_rq_list bottom up

In reply to Rik van Riel

Reducing 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
index aebd43d74468..dcc521d251e3 100644
@@ -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
index 5be14cee61f9..18494b1a9bac 100644
@@ -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
#11 lore raw

PATCH 5/8 sched,cfs: use explicit cfs_rq of parent se helper

In reply to Rik van Riel

Use 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
index dcc521d251e3..c6ede2ecc935 100644
@@ -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
#12 lore raw

Re: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper

Quoted 41 lines · Rik van Riel

Use 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 +10 -1
index dcc521d251e3..c6ede2ecc935 100644
@@ -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;

[...]

#13 lore raw

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_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 +9 -0
index dcc521d251e3..c6ede2ecc935 100644
@@ -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 -1
 	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)
 
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 -1
 	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.

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 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.

(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.
#14 lore raw

Re: [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() 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.

Quoted 7 lines

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.

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 first for_each_sched_entity() loop
we should still start with group_cfs_rq() (se->my_q) ?

Here I was wrong. The first loop did use cfs_rq_of() and not group_cfs_rq(). [...]

#15 lore raw

Re: [PATCH 5/8] sched,cfs: use explicit cfs_rq of parent se helper

In reply to Rik van Riel
Quoted 16 lines · Rik van Riel

Use 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 +0 -0
index dcc521d251e3..c6ede2ecc935 100644

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.

[...]

#16 lore raw

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_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 +0 -0
index dcc521d251e3..c6ede2ecc935 100644
@@ -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 (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;
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.
#17 lore raw

PATCH 6/8 sched,cfs: fix zero length timeslice calculation

In reply to Rik van Riel

The way the time slice length is currently calculated, not only do high priority tasks get longer time slices than low priority tasks, but due to fixed point math, low priority tasks could end up with a zero length time slice. This can lead to cache thrashing and other inefficiencies.

Simplify the logic a little bit, and cap the minimum time slice length to sysctl_sched_min_granularity.

Tasks that end up getting a time slice length too long for their relative priority will simply end up having their vruntime advanced much faster than other tasks, resulting in them receiving time slices less frequently.

---
 kernel/sched/fair.c | 25 ++++++++-----------------
 1 file changed, 8 insertions(+), 17 deletions(-)
kernel/sched/fair.c +8 -17
index c6ede2ecc935..35153a89d5c5 100644
@@ -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
#18 lore raw

PATCH 7/8 sched,fair: refactor enqueue/dequeue_entity

In reply to Rik van Riel

Refactor 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
index 35153a89d5c5..c2baf3c8a879 100644
@@ -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
#19 lore raw

PATCH 8/8 sched,fair: flatten hierarchical runqueues

In reply to Rik van Riel

Flatten 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
index f5bb6948e40c..05ed40b304dc 100644
@@ -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
index 32dc2791a517..45d3b4979022 100644
@@ -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
index 7489d5f56960..1152c4ebf314 100644
@@ -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
index 18494b1a9bac..67066daf7ee9 100644
@@ -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
#20 lore raw

Re: [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

...

[...]

#21 lore raw

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 existing parent_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) and se->load.weight are 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.
#22 lore raw

Re: [PATCH 8/8] sched,fair: flatten hierarchical runqueues

In reply to Rik van Riel
Quoted 21 lines · Rik van Riel

Flatten 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(-)

[...]

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.

[...]

#23 lore raw

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_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(-)

[...]

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, struct sched_entity *s
* track group sched_entity load average for task_h_load calc
in migration

kernel/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 use
cfs_rq = se->cfs_rq (i.e. root cfs_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.