Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1623048 > unrolled thread

[RFC 0/3] sched/topology: fix sched groups on NUMA machines with mesh topology

Back to article view | Back to linux.kernel

Contents

  [RFC 0/3] sched/topology: fix sched groups on NUMA machines with mesh topology Lauro Ramos Venancio <lvenanci@redhat.com> - 2017-04-13 16:00 +0200
    [RFC 1/3] sched/topology: Refactor function build_overlap_sched_groups() Lauro Ramos Venancio <lvenanci@redhat.com> - 2017-04-13 16:00 +0200
      Re: [RFC 1/3] sched/topology: Refactor function  build_overlap_sched_groups() Rik van Riel <riel@redhat.com> - 2017-04-13 17:00 +0200
    [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu Lauro Ramos Venancio <lvenanci@redhat.com> - 2017-04-13 16:00 +0200
      Re: [RFC 3/3] sched/topology: Different sched groups must not have  the same balance cpu Rik van Riel <riel@redhat.com> - 2017-04-13 17:30 +0200
      Re: [RFC 3/3] sched/topology: Different sched groups must not have  the same balance cpu Peter Zijlstra <peterz@infradead.org> - 2017-04-14 18:50 +0200
        Re: [RFC 3/3] sched/topology: Different sched groups must not have  the same balance cpu Lauro Venancio <lvenanci@redhat.com> - 2017-04-17 17:40 +0200
          Re: [RFC 3/3] sched/topology: Different sched groups must not have  the same balance cpu Peter Zijlstra <peterz@infradead.org> - 2017-04-18 14:40 +0200

#1623048 — [RFC 0/3] sched/topology: fix sched groups on NUMA machines with mesh topology

Currently, the scheduler is not able to directly move tasks between some NUMA
nodes 2-hops apart on machines with mesh topology. This occurs because some
NUMA nodes belongs to all sched groups. For more details, see the patch 2
commit log.

This bug was reported in the paper [1] as "The Scheduling Group Construction
bug".

This patchset constructs the sched groups from each CPU perspective. So each
NUMA node can have different groups in the last NUMA sched domain level.

SPECjbb2005 results show up to 63% performance improvement and a huge standard
deviation drop on a machine with 8 NUMA nodes and mesh topology.

Patch 1 - just prepare the code for patch 2
Patch 2 - change the sched groups construction
Patch 3 - fix issue with different groups starting with the same CPU

[1] http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf

Regards,
Lauro

Lauro Ramos Venancio (3):
  sched/topology: Refactor function build_overlap_sched_groups()
  sched/topology: fix sched groups on NUMA machines with mesh topology
  sched/topology: Different sched groups must not have the same balance
    cpu

 kernel/sched/topology.c | 165 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 117 insertions(+), 48 deletions(-)

-- 
1.8.3.1

[toc] | [next] | [standalone]

#1623053 — [RFC 1/3] sched/topology: Refactor function build_overlap_sched_groups()

Create functions build_group_from_child_sched_domain() and
init_overlap_sched_group(). No functional change.

Signed-off-by: Lauro Ramos Venancio <lvenanci@redhat.com>
---
 kernel/sched/topology.c | 62 ++++++++++++++++++++++++++++++++++---------------
 1 file changed, 43 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 1b0b4fb..d786d45 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -513,6 +513,47 @@ int group_balance_cpu(struct sched_group *sg)
 	return cpumask_first_and(sched_group_cpus(sg), sched_group_mask(sg));
 }
 
+static struct sched_group *
+build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
+{
+	struct sched_group *sg;
+	struct cpumask *sg_span;
+
+	sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
+			GFP_KERNEL, cpu_to_node(cpu));
+
+	if (!sg)
+		return NULL;
+
+	sg_span = sched_group_cpus(sg);
+	if (sd->child)
+		cpumask_copy(sg_span, sched_domain_span(sd->child));
+	else
+		cpumask_copy(sg_span, sched_domain_span(sd));
+
+	return sg;
+}
+
+static void init_overlap_sched_group(struct sched_domain *sd,
+				     struct sched_group *sg, int cpu)
+{
+	struct sd_data *sdd = sd->private;
+	struct cpumask *sg_span;
+
+	sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
+	if (atomic_inc_return(&sg->sgc->ref) == 1)
+		build_group_mask(sd, sg);
+
+	/*
+	 * Initialize sgc->capacity such that even if we mess up the
+	 * domains and no possible iteration will get us here, we won't
+	 * die on a /0 trap.
+	 */
+	sg_span = sched_group_cpus(sg);
+	sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
+	sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
+}
+
 static int
 build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 {
@@ -537,31 +578,14 @@ int group_balance_cpu(struct sched_group *sg)
 		if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
 			continue;
 
-		sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
-				GFP_KERNEL, cpu_to_node(cpu));
-
+		sg = build_group_from_child_sched_domain(sibling, cpu);
 		if (!sg)
 			goto fail;
 
 		sg_span = sched_group_cpus(sg);
-		if (sibling->child)
-			cpumask_copy(sg_span, sched_domain_span(sibling->child));
-		else
-			cpumask_set_cpu(i, sg_span);
-
 		cpumask_or(covered, covered, sg_span);
 
-		sg->sgc = *per_cpu_ptr(sdd->sgc, i);
-		if (atomic_inc_return(&sg->sgc->ref) == 1)
-			build_group_mask(sd, sg);
-
-		/*
-		 * Initialize sgc->capacity such that even if we mess up the
-		 * domains and no possible iteration will get us here, we won't
-		 * die on a /0 trap.
-		 */
-		sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
-		sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
+		init_overlap_sched_group(sd, sg, i);
 
 		/*
 		 * Make sure the first group of this domain contains the
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1623097 — Re: [RFC 1/3] sched/topology: Refactor function build_overlap_sched_groups()

On Thu, 2017-04-13 at 10:56 -0300, Lauro Ramos Venancio wrote:
> Create functions build_group_from_child_sched_domain() and
> init_overlap_sched_group(). No functional change.
> 
> Signed-off-by: Lauro Ramos Venancio <lvenanci@redhat.com>
> 
Acked-by: Rik van Riel <riel@redhat.com>

[toc] | [prev] | [next] | [standalone]

#1623055 — [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu

Currently, the group balance cpu is the groups's first CPU. But with
overlapping groups, two different groups can have the same first CPU.

This patch uses the group mask to mark all the CPUs that have a
particular group as its main sched group. The group balance cpu is the
first group CPU that is also in the mask.

Signed-off-by: Lauro Ramos Venancio <lvenanci@redhat.com>
---
 kernel/sched/topology.c | 76 ++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 62 insertions(+), 14 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index d0302ad..7920bbb 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -477,27 +477,31 @@ enum s_alloc {
 };
 
 /*
- * Build an iteration mask that can exclude certain CPUs from the upwards
- * domain traversal.
+ * An overlap sched group may not be present in all CPUs that compose the
+ * group. So build the mask, marking all the group CPUs where it is present.
  *
  * Asymmetric node setups can result in situations where the domain tree is of
  * unequal depth, make sure to skip domains that already cover the entire
  * range.
- *
- * In that case build_sched_domains() will have terminated the iteration early
- * and our sibling sd spans will be empty. Domains should always include the
- * CPU they're built on, so check that.
  */
 static void build_group_mask(struct sched_domain *sd, struct sched_group *sg)
 {
-	const struct cpumask *span = sched_domain_span(sd);
+	const struct cpumask *sg_span = sched_group_cpus(sg);
 	struct sd_data *sdd = sd->private;
 	struct sched_domain *sibling;
 	int i;
 
-	for_each_cpu(i, span) {
+	for_each_cpu(i, sg_span) {
 		sibling = *per_cpu_ptr(sdd->sd, i);
-		if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
+
+		/*
+		 * Asymmetric node setups: skip domains that are already
+		 * done.
+		 */
+		if (!sibling->groups)
+			continue;
+
+		if (!cpumask_equal(sg_span, sched_group_cpus(sibling->groups)))
 			continue;
 
 		cpumask_set_cpu(i, sched_group_mask(sg));
@@ -513,6 +517,28 @@ int group_balance_cpu(struct sched_group *sg)
 	return cpumask_first_and(sched_group_cpus(sg), sched_group_mask(sg));
 }
 
+/*
+ * Find the group balance cpu when the group mask is not available yet.
+ */
+static int find_group_balance_cpu(struct sched_domain *sd,
+				  struct sched_group *sg)
+{
+	const struct cpumask *sg_span = sched_group_cpus(sg);
+	struct sd_data *sdd = sd->private;
+	struct sched_domain *sibling;
+	int i;
+
+	for_each_cpu(i, sg_span) {
+		sibling = *per_cpu_ptr(sdd->sd, i);
+		if (cpumask_equal(sg_span, sched_group_cpus(sibling->groups)))
+			return i;
+	}
+
+	WARN(1, "group balance cpu not found.");
+	return 0;
+}
+
+
 static struct sched_group *
 build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
 {
@@ -554,6 +580,19 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 	sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
 }
 
+static void init_overlap_sched_groups(struct sched_domain *sd)
+{
+	struct sched_group *sg = sd->groups;
+	int cpu;
+
+	do {
+		cpu = find_group_balance_cpu(sd, sg);
+		init_overlap_sched_group(sd, sg, cpu);
+
+		sg = sg->next;
+	} while (sg != sd->groups);
+}
+
 static int
 build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 {
@@ -568,8 +607,6 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 	if (!sg)
 		return -ENOMEM;
 
-	init_overlap_sched_group(sd, sg, cpu);
-
 	sd->groups = sg;
 	last = sg;
 	sg->next = sg;
@@ -584,7 +621,12 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 
 		sibling = *per_cpu_ptr(sdd->sd, i);
 
-		/* See the comment near build_group_mask(). */
+		/*
+		 * In Asymmetric node setups, build_sched_domains() will have
+		 * terminated the iteration early and our sibling sd spans will
+		 * be empty. Domains should always include the CPU they're
+		 * built on, so check that.
+		 */
 		if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
 			continue;
 
@@ -595,8 +637,6 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 		sg_span = sched_group_cpus(sg);
 		cpumask_or(covered, covered, sg_span);
 
-		init_overlap_sched_group(sd, sg, i);
-
 		last->next = sg;
 		last = sg;
 		sg->next = sd->groups;
@@ -1449,6 +1489,14 @@ struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
 		}
 	}
 
+	/* Init overlap groups */
+	for_each_cpu(i, cpu_map) {
+		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+			if (sd->flags & SD_OVERLAP)
+				init_overlap_sched_groups(sd);
+		}
+	}
+
 	/* Calculate CPU capacity for physical packages and nodes */
 	for (i = nr_cpumask_bits-1; i >= 0; i--) {
 		if (!cpumask_test_cpu(i, cpu_map))
-- 
1.8.3.1

[toc] | [prev] | [next] | [standalone]

#1623121 — Re: [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu

On Thu, 2017-04-13 at 10:56 -0300, Lauro Ramos Venancio wrote:
> Currently, the group balance cpu is the groups's first CPU. But with
> overlapping groups, two different groups can have the same first CPU.
> 
> This patch uses the group mask to mark all the CPUs that have a
> particular group as its main sched group. The group balance cpu is
> the
> first group CPU that is also in the mask.
> 

This is not your fault, but this code is really hard
to understand.

Your comments tell me what the code does, but not
really why. 

> +++ b/kernel/sched/topology.c
> @@ -477,27 +477,31 @@ enum s_alloc {
>  };
>  
>  /*
> - * Build an iteration mask that can exclude certain CPUs from the
> upwards
> - * domain traversal.
> + * An overlap sched group may not be present in all CPUs that
> compose the
> + * group. So build the mask, marking all the group CPUs where it is
> present.
>   *
>   * Asymmetric node setups can result in situations where the domain
> tree is of
>   * unequal depth, make sure to skip domains that already cover the
> entire
>   * range.
> - *
> - * In that case build_sched_domains() will have terminated the
> iteration early
> - * and our sibling sd spans will be empty. Domains should always
> include the
> - * CPU they're built on, so check that.
>   */

Why are we doing this?

Could the comment explain why things need to be
this way?


> -	for_each_cpu(i, span) {
> +	for_each_cpu(i, sg_span) {
>  		sibling = *per_cpu_ptr(sdd->sd, i);
> -		if (!cpumask_test_cpu(i,
> sched_domain_span(sibling)))
> +
> +		/*
> +		 * Asymmetric node setups: skip domains that are
> already
> +		 * done.
> +		 */
> +		if (!sibling->groups)
> +			continue;
> +

What does this mean?

I would really like it if this code was a little
better documented.  This is not something I can
put on you for most of the code, but I can at least
ask it for the code you are adding :)

The same goes for the rest of this patch.

[toc] | [prev] | [next] | [standalone]

#1623767 — Re: [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu

On Thu, Apr 13, 2017 at 10:56:09AM -0300, Lauro Ramos Venancio wrote:
> Currently, the group balance cpu is the groups's first CPU. But with
> overlapping groups, two different groups can have the same first CPU.
> 
> This patch uses the group mask to mark all the CPUs that have a
> particular group as its main sched group. The group balance cpu is the
> first group CPU that is also in the mask.

Please give a NUMA configuration and CPU number where this goes wrong.

Because only the first group of a domain matters, and with the other
thing fixed, I'm not immediately seeing where we go wobbly.

[toc] | [prev] | [next] | [standalone]

#1624714 — Re: [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu

On 04/14/2017 01:49 PM, Peter Zijlstra wrote:
> On Thu, Apr 13, 2017 at 10:56:09AM -0300, Lauro Ramos Venancio wrote:
>> Currently, the group balance cpu is the groups's first CPU. But with
>> overlapping groups, two different groups can have the same first CPU.
>>
>> This patch uses the group mask to mark all the CPUs that have a
>> particular group as its main sched group. The group balance cpu is the
>> first group CPU that is also in the mask.
> Please give a NUMA configuration and CPU number where this goes wrong.
On a 4 nodes with ring topology, the groups (0-1,3 [cpu 0]),  (0-2 [cpu
1]) and (0,2-3 [cpu 3]) share the same sched_group_capacity instance
when the first groups cpu is used to select the sgc.
>
> Because only the first group of a domain matters, and with the other
> thing fixed, I'm not immediately seeing where we go wobbly.

Before patch 2, the group balance cpu was implicitly used to select the
sched_group_capacity instance. When two different groups had the same
balance cpu, they shared the same sched_group_capacity instance.

After patch 2, one different sched_group_capacity instance is assigned
to each group instance.


This patch ensures tree things:

1) different instances of the same group share the same
sched_group_capacity instance.

2) instances of different groups don't share the same
sched_group_capacity instance.

3) the group balance cpu must be one of the cpus where the group is
installed.


I am rebasing this patch on top of your patches.

[toc] | [prev] | [next] | [standalone]

#1625297 — Re: [RFC 3/3] sched/topology: Different sched groups must not have the same balance cpu

On Mon, Apr 17, 2017 at 12:34:05PM -0300, Lauro Venancio wrote:
> This patch ensures tree things:
> 
> 1) different instances of the same group share the same
> sched_group_capacity instance.
> 
> 2) instances of different groups don't share the same
> sched_group_capacity instance.
> 
> 3) the group balance cpu must be one of the cpus where the group is
> installed.
> 
> 
> I am rebasing this patch on top of your patches.

Well, I would rather have 3 patches, each with a comprehensible
changelog.

I had already rebased the patch (trivial) so that's not the problem.
Explaining what and why it does things is.

And as per the usual rules, if it does 3 things it should be 3 patches.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web