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

Groups > linux.kernel > #1623046 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology Lauro Ramos Venancio <lvenanci@redhat.com> - 2017-04-13 16:00 +0200
    Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines  with mesh topology Rik van Riel <riel@redhat.com> - 2017-04-13 17:20 +0200
    Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Peter Zijlstra <peterz@infradead.org> - 2017-04-13 17:50 +0200
      Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Lauro Venancio <lvenanci@redhat.com> - 2017-04-13 22:30 +0200
        Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Lauro Venancio <lvenanci@redhat.com> - 2017-04-13 23:10 +0200
          Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines  with mesh topology Rik van Riel <riel@redhat.com> - 2017-04-14 01:40 +0200
            Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Peter Zijlstra <peterz@infradead.org> - 2017-04-14 12:50 +0200
    Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Peter Zijlstra <peterz@infradead.org> - 2017-04-14 13:40 +0200
      Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Peter Zijlstra <peterz@infradead.org> - 2017-04-14 14:30 +0200
      Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Peter Zijlstra <peterz@infradead.org> - 2017-04-14 19:00 +0200
        Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with  mesh topology Lauro Venancio <lvenanci@redhat.com> - 2017-04-17 16:50 +0200

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

Currently, on a 4 nodes NUMA machine with ring topology, two sched
groups are generated for the last NUMA sched domain. One group has the
CPUs from NUMA nodes 3, 0 and 1; the other group has the CPUs from nodes
1, 2 and 3. As CPUs from nodes 1 and 3 belongs to both groups, the
scheduler is unable to directly move tasks between these nodes. In the
worst scenario, when a set of tasks are bound to nodes 1 and 3, the
performance is severely impacted because just one node is used while the
other node remains idle.

This problem also affects machines with more NUMA nodes. For instance,
currently, the scheduler is unable to directly move tasks between some
node pairs 2-hops apart on an 8 nodes machine with mesh topology.

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

This patch constructs the sched groups from each CPU perspective. So, on
a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
[(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
apart.

SPECjbb2005 results on an 8 NUMA nodes machine with mesh topology

Threads       before              after          %
           mean   stddev      mean    stddev
  1       22801   1950        27059   1367     +19%
  8       146008  50782       209193  826      +43%
  32      351030  105111      522445  9051     +49%
  48      365835  116571      594905  3314     +63%

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

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

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index d786d45..d0302ad 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -557,14 +557,24 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 static int
 build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 {
-	struct sched_group *first = NULL, *last = NULL, *groups = NULL, *sg;
+	struct sched_group *last = NULL, *sg;
 	const struct cpumask *span = sched_domain_span(sd);
 	struct cpumask *covered = sched_domains_tmpmask;
 	struct sd_data *sdd = sd->private;
 	struct sched_domain *sibling;
 	int i;
 
-	cpumask_clear(covered);
+	sg = build_group_from_child_sched_domain(sd, cpu);
+	if (!sg)
+		return -ENOMEM;
+
+	init_overlap_sched_group(sd, sg, cpu);
+
+	sd->groups = sg;
+	last = sg;
+	sg->next = sg;
+
+	cpumask_copy(covered, sched_group_cpus(sg));
 
 	for_each_cpu(i, span) {
 		struct cpumask *sg_span;
@@ -587,28 +597,15 @@ static void init_overlap_sched_group(struct sched_domain *sd,
 
 		init_overlap_sched_group(sd, sg, i);
 
-		/*
-		 * Make sure the first group of this domain contains the
-		 * canonical balance CPU. Otherwise the sched_domain iteration
-		 * breaks. See update_sg_lb_stats().
-		 */
-		if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
-		    group_balance_cpu(sg) == cpu)
-			groups = sg;
-
-		if (!first)
-			first = sg;
-		if (last)
-			last->next = sg;
+		last->next = sg;
 		last = sg;
-		last->next = first;
+		sg->next = sd->groups;
 	}
-	sd->groups = groups;
 
 	return 0;
 
 fail:
-	free_sched_groups(first, 0);
+	free_sched_groups(sd->groups, 0);
 
 	return -ENOMEM;
 }
-- 
1.8.3.1

[toc] | [next] | [standalone]

#1623116 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Thu, 2017-04-13 at 10:56 -0300, Lauro Ramos Venancio wrote:
> 
> SPECjbb2005 results on an 8 NUMA nodes machine with mesh topology
> 
> Threads       before              after          %
>            mean   stddev      mean    stddev
>   1       22801   1950        27059   1367     +19%
>   8       146008  50782       209193  826      +43%
>   32      351030  105111      522445  9051     +49%
>   48      365835  116571      594905  3314     +63%

Impressive!

> [1] http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf
> 
> Signed-off-by: Lauro Ramos Venancio <lvenanci@redhat.com>

Acked-by: Rik van Riel <riel@redhat.com>

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

#1623136 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
> Currently, on a 4 nodes NUMA machine with ring topology, two sched
> groups are generated for the last NUMA sched domain. One group has the
> CPUs from NUMA nodes 3, 0 and 1; the other group has the CPUs from nodes
> 1, 2 and 3. As CPUs from nodes 1 and 3 belongs to both groups, the
> scheduler is unable to directly move tasks between these nodes. In the
> worst scenario, when a set of tasks are bound to nodes 1 and 3, the
> performance is severely impacted because just one node is used while the
> other node remains idle.

I feel a picture would be ever so much clearer.

> This patch constructs the sched groups from each CPU perspective. So, on
> a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
> groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
> [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
> apart.

So I still have no idea what specifically goes wrong and how this fixes
it. Changelog is impenetrable.

"From each CPU's persepective" doesn't really help, there already is a
for_each_cpu() in.

Also, since I'm not sure what happend to the 4 node system, I cannot
begin to imagine what would happen on the 8 node one.

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

#1623333 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On 04/13/2017 12:48 PM, Peter Zijlstra wrote:
> On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
>> Currently, on a 4 nodes NUMA machine with ring topology, two sched
>> groups are generated for the last NUMA sched domain. One group has the
>> CPUs from NUMA nodes 3, 0 and 1; the other group has the CPUs from nodes
>> 1, 2 and 3. As CPUs from nodes 1 and 3 belongs to both groups, the
>> scheduler is unable to directly move tasks between these nodes. In the
>> worst scenario, when a set of tasks are bound to nodes 1 and 3, the
>> performance is severely impacted because just one node is used while the
>> other node remains idle.
> I feel a picture would be ever so much clearer.
>
>> This patch constructs the sched groups from each CPU perspective. So, on
>> a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
>> groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
>> [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
>> apart.
> So I still have no idea what specifically goes wrong and how this fixes
> it. Changelog is impenetrable.
On a 4 nodes machine with ring topology, the last sched domain level
contains groups with 3 numa nodes each. So we have four possible groups:
(0, 1, 2) (1, 2, 3) (2, 3, 0)(3, 0, 1). As we need just two groups to
fill the sched domain, currently, the groups (3, 0, 1) and (1, 2, 3) are
used for all CPUs. The problem with it is that nodes 1 and 3 belongs to
both groups, becoming impossible to move tasks between these two nodes.

This patch uses different groups depending on the CPU they are
installed. So nodes 0 and 2 CPUs keep the same group as before: (3, 0,
1) and (1, 2, 3). Nodes 1 and 3 CPUs use the new groups: (0, 1, 2) and
(2, 3, 0). So the first pair of groups allows movement between nodes 0
and 2; and the second pair of groups allows movement between nodes 1 and 3.

I will improve the changelog.

> "From each CPU's persepective" doesn't really help, there already is a
> for_each_cpu() in.
The for_each_cpu() is used to iterate across all sched domain cpus. It
doesn't consider the CPU where the groups are being installed (parameter
cpu in build_overlap_sched_groups()). Currently, the parameter cpu is
used just for memory allocation and for ordering the groups, it doesn't
change the groups that are chosen. This patch uses the parameter cpu to
choose the first group, changing also, as consequence, the second group.
>
> Also, since I'm not sure what happend to the 4 node system, I cannot
> begin to imagine what would happen on the 8 node one.

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

#1623352 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On 04/13/2017 05:21 PM, Lauro Venancio wrote:
> On 04/13/2017 12:48 PM, Peter Zijlstra wrote:
>> On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
>>> Currently, on a 4 nodes NUMA machine with ring topology, two sched
>>> groups are generated for the last NUMA sched domain. One group has the
>>> CPUs from NUMA nodes 3, 0 and 1; the other group has the CPUs from nodes
>>> 1, 2 and 3. As CPUs from nodes 1 and 3 belongs to both groups, the
>>> scheduler is unable to directly move tasks between these nodes. In the
>>> worst scenario, when a set of tasks are bound to nodes 1 and 3, the
>>> performance is severely impacted because just one node is used while the
>>> other node remains idle.
>> I feel a picture would be ever so much clearer.
>>
>>> This patch constructs the sched groups from each CPU perspective. So, on
>>> a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
>>> groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
>>> [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
>>> apart.
>> So I still have no idea what specifically goes wrong and how this fixes
>> it. Changelog is impenetrable.
> On a 4 nodes machine with ring topology, the last sched domain level
> contains groups with 3 numa nodes each. So we have four possible groups:
> (0, 1, 2) (1, 2, 3) (2, 3, 0)(3, 0, 1). As we need just two groups to
> fill the sched domain, currently, the groups (3, 0, 1) and (1, 2, 3) are
> used for all CPUs. The problem with it is that nodes 1 and 3 belongs to
> both groups, becoming impossible to move tasks between these two nodes.
>
> This patch uses different groups depending on the CPU they are
> installed. So nodes 0 and 2 CPUs keep the same group as before: (3, 0,
> 1) and (1, 2, 3). Nodes 1 and 3 CPUs use the new groups: (0, 1, 2) and
> (2, 3, 0). So the first pair of groups allows movement between nodes 0
> and 2; and the second pair of groups allows movement between nodes 1 and 3.
>
> I will improve the changelog.
>
>> "From each CPU's persepective" doesn't really help, there already is a
>> for_each_cpu() in.
> The for_each_cpu() is used to iterate across all sched domain cpus. It
> doesn't consider the CPU where the groups are being installed (parameter
> cpu in build_overlap_sched_groups()). Currently, the parameter cpu is
> used just for memory allocation and for ordering the groups, it doesn't
> change the groups that are chosen. This patch uses the parameter cpu to
> choose the first group, changing also, as consequence, the second group.
>> Also, since I'm not sure what happend to the 4 node system, I cannot
>> begin to imagine what would happen on the 8 node one.

Just for clarification, I am sending the nodes distance table for the
two most common typologies affected by this issue.

4 nodes, ring topology
node distances:
node   0   1   2   3
  0:  10  20  30  20
  1:  20  10  20  30
  2:  30  20  10  20
  3:  20  30  20  10

8 node, mesh topology
node distances:
node   0   1   2   3   4   5   6   7
  0:  10  16  16  22  16  22  16  22
  1:  16  10  16  22  22  16  22  16
  2:  16  16  10  16  16  16  16  22
  3:  22  22  16  10  16  16  22  16
  4:  16  22  16  16  10  16  16  16
  5:  22  16  16  16  16  10  22  22
  6:  16  22  16  22  16  22  10  16
  7:  22  16  22  16  16  22  16  10

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

#1623426 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Thu, 2017-04-13 at 18:06 -0300, Lauro Venancio wrote:

> Just for clarification, I am sending the nodes distance table for the
> two most common typologies affected by this issue.

What do the sched groups look like for these topologies,
before and after your patch series?

> 4 nodes, ring topology
> node distances:
> node   0   1   2   3
>   0:  10  20  30  20
>   1:  20  10  20  30
>   2:  30  20  10  20
>   3:  20  30  20  10
> 
> 8 node, mesh topology
> node distances:
> node   0   1   2   3   4   5   6   7
>   0:  10  16  16  22  16  22  16  22
>   1:  16  10  16  22  22  16  22  16
>   2:  16  16  10  16  16  16  16  22
>   3:  22  22  16  10  16  16  22  16
>   4:  16  22  16  16  10  16  16  16
>   5:  22  16  16  16  16  10  22  22
>   6:  16  22  16  22  16  22  10  16
>   7:  22  16  22  16  16  22  16  10

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

#1623636 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Thu, Apr 13, 2017 at 07:38:05PM -0400, Rik van Riel wrote:

> What do the sched groups look like for these topologies,
> before and after your patch series?
> 
> > 4 nodes, ring topology
> > node distances:
> > node   0   1   2   3
> >   0:  10  20  30  20
> >   1:  20  10  20  30
> >   2:  30  20  10  20
> >   3:  20  30  20  10

kvm -smp 4 -m 4G -display none -monitor null -serial stdio -kernel
defconfig-build/arch/x86/boot/bzImage -append "sched_debug debug
ignore_loglevel earlyprintk=serial,ttyS0,115200,keep
numa=fake=4:10,20,30,20,20,10,20,30,30,20,10,20,20,30,20,10,0"

(FWIW, that's defconfig+kvmconfig+SCHED_DEBUG=y+NUMA_EMU=y)

Gives me:

[    0.075004] smpboot: Total of 4 processors activated (22345.79 BogoMIPS)
[    0.076767] CPU0 attaching sched-domain:
[    0.077003]  domain 0: span 0-1,3 level NUMA
[    0.078002]   groups: 0 1 3
[    0.079002]   domain 1: span 0-3 level NUMA
[    0.080002]    groups: 0-1,3 (cpu_capacity = 3072) 1-3 (cpu_capacity = 3072)
[    0.081005] CPU1 attaching sched-domain:
[    0.082003]  domain 0: span 0-2 level NUMA
[    0.083002]   groups: 1 2 0
[    0.084002]   domain 1: span 0-3 level NUMA
[    0.085002]    groups: 1-3 (cpu_capacity = 3072) 0-1,3 (cpu_capacity = 3072)
[    0.086004] CPU2 attaching sched-domain:
[    0.087002]  domain 0: span 1-3 level NUMA
[    0.088002]   groups: 2 3 1
[    0.089002]   domain 1: span 0-3 level NUMA
[    0.090002]    groups: 1-3 (cpu_capacity = 3072) 0-1,3 (cpu_capacity = 3072)
[    0.091004] CPU3 attaching sched-domain:
[    0.092002]  domain 0: span 0,2-3 level NUMA
[    0.093002]   groups: 3 0 2
[    0.094002]   domain 1: span 0-3 level NUMA
[    0.095002]    groups: 0-1,3 (cpu_capacity = 3072) 1-3 (cpu_capacity = 3072)
[    0.096004] span: 0-3 (max cpu_capacity = 1024)


With patches it looks like:

[    0.080006] smpboot: Total of 4 processors activated (22345.79 BogoMIPS)
[    0.082545] CPU0 attaching sched-domain:
[    0.083007]  domain 0: span 0-1,3 level NUMA
[    0.084004]   groups: 0 1 3
[    0.085004]   domain 1: span 0-3 level NUMA
[    0.086004]    groups: 0-1,3 (cpu_capacity = 3072) 1-3 (cpu_capacity = 3072)
[    0.087007] CPU1 attaching sched-domain:
[    0.088004]  domain 0: span 0-2 level NUMA
[    0.089004]   groups: 1 0 2
[    0.090004]   domain 1: span 0-3 level NUMA
[    0.091003]    groups: 0-2 (cpu_capacity = 3072) 0,2-3 (cpu_capacity = 3072)
[    0.092008] CPU2 attaching sched-domain:
[    0.093004]  domain 0: span 1-3 level NUMA
[    0.094004]   groups: 2 1 3
[    0.095004]   domain 1: span 0-3 level NUMA
[    0.096004]    groups: 1-3 (cpu_capacity = 3072) 0-1,3 (cpu_capacity = 3072)
[    0.097007] CPU3 attaching sched-domain:
[    0.098004]  domain 0: span 0,2-3 level NUMA
[    0.099003]   groups: 3 0 2
[    0.100004]   domain 1: span 0-3 level NUMA
[    0.101003]    groups: 0,2-3 (cpu_capacity = 3072) 0-2 (cpu_capacity = 3072)
[    0.102007] span: 0-3 (max cpu_capacity = 1024)


Now let me try and reverse engineer those patches ..

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

#1623639 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
> This patch constructs the sched groups from each CPU perspective. So, on
> a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
> groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
> [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
> apart.

Ah,.. so after drawing pictures I see what went wrong; duh :-(

An equivalent patch would be (if for_each_cpu_wrap() were exposed):

@@ -521,11 +588,11 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 	struct cpumask *covered = sched_domains_tmpmask;
 	struct sd_data *sdd = sd->private;
 	struct sched_domain *sibling;
-	int i;
+	int i, wrap;
 
 	cpumask_clear(covered);
 
-	for_each_cpu(i, span) {
+	for_each_cpu_wrap(i, span, cpu, wrap) {
 		struct cpumask *sg_span;
 
 		if (cpumask_test_cpu(i, covered))


We need to start iterating at @cpu, not start at 0 every time.

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

#1623651 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Fri, Apr 14, 2017 at 01:38:13PM +0200, Peter Zijlstra wrote:

> An equivalent patch would be (if for_each_cpu_wrap() were exposed):

---
Subject: sched,cpumask: Export for_each_cpu_wrap()

More users for for_each_cpu_wrap() have appeared. Promote the construct
to generic cpumask interface.

The implementation is slightly modified to reduce arguments.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 include/linux/cpumask.h | 16 ++++++++++++++++
 kernel/sched/fair.c     | 45 ++++-----------------------------------------
 lib/cpumask.c           | 32 ++++++++++++++++++++++++++++++++
 3 files changed, 52 insertions(+), 41 deletions(-)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 96f1e88..4b87b7b 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -236,6 +236,22 @@ unsigned int cpumask_local_spread(unsigned int i, int node);
 		(cpu) = cpumask_next_zero((cpu), (mask)),	\
 		(cpu) < nr_cpu_ids;)
 
+
+/**
+ * for_each_cpu_wrap - iterate over every cpu in a mask, starting at a specified location
+ * @cpu: the (optionally unsigned) integer iterator
+ * @mask: the cpumask poiter
+ * @start: the start location
+ *
+ * The implementation does not assume any bit in @mask is set (including @start).
+ *
+ * After the loop, cpu is >= nr_cpu_ids.
+ */
+#define for_each_cpu_wrap(cpu, mask, start)					\
+	for ((cpu) = cpumask_next_wrap((start)-1, (mask), (start), false);	\
+	     (cpu) < nr_cpumask_bits;						\
+	     (cpu) = cpumask_next_wrap((cpu), (mask), (start), true))
+
 /**
  * for_each_cpu_and - iterate over every cpu in both masks
  * @cpu: the (optionally unsigned) integer iterator
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a903276..d89d700 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5640,43 +5640,6 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
 	return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
 }
 
-/*
- * Implement a for_each_cpu() variant that starts the scan at a given cpu
- * (@start), and wraps around.
- *
- * This is used to scan for idle CPUs; such that not all CPUs looking for an
- * idle CPU find the same CPU. The down-side is that tasks tend to cycle
- * through the LLC domain.
- *
- * Especially tbench is found sensitive to this.
- */
-
-static int cpumask_next_wrap(int n, const struct cpumask *mask, int start, int *wrapped)
-{
-	int next;
-
-again:
-	next = find_next_bit(cpumask_bits(mask), nr_cpumask_bits, n+1);
-
-	if (*wrapped) {
-		if (next >= start)
-			return nr_cpumask_bits;
-	} else {
-		if (next >= nr_cpumask_bits) {
-			*wrapped = 1;
-			n = -1;
-			goto again;
-		}
-	}
-
-	return next;
-}
-
-#define for_each_cpu_wrap(cpu, mask, start, wrap)				\
-	for ((wrap) = 0, (cpu) = (start)-1;					\
-		(cpu) = cpumask_next_wrap((cpu), (mask), (start), &(wrap)),	\
-		(cpu) < nr_cpumask_bits; )
-
 #ifdef CONFIG_SCHED_SMT
 
 static inline void set_idle_cores(int cpu, int val)
@@ -5736,7 +5699,7 @@ void __update_idle_core(struct rq *rq)
 static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int target)
 {
 	struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask);
-	int core, cpu, wrap;
+	int core, cpu;
 
 	if (!static_branch_likely(&sched_smt_present))
 		return -1;
@@ -5746,7 +5709,7 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int
 
 	cpumask_and(cpus, sched_domain_span(sd), &p->cpus_allowed);
 
-	for_each_cpu_wrap(core, cpus, target, wrap) {
+	for_each_cpu_wrap(core, cpus, target) {
 		bool idle = true;
 
 		for_each_cpu(cpu, cpu_smt_mask(core)) {
@@ -5812,7 +5775,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 	u64 avg_cost, avg_idle = this_rq()->avg_idle;
 	u64 time, cost;
 	s64 delta;
-	int cpu, wrap;
+	int cpu;
 
 	this_sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
 	if (!this_sd)
@@ -5829,7 +5792,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 
 	time = local_clock();
 
-	for_each_cpu_wrap(cpu, sched_domain_span(sd), target, wrap) {
+	for_each_cpu_wrap(cpu, sched_domain_span(sd), target) {
 		if (!cpumask_test_cpu(cpu, &p->cpus_allowed))
 			continue;
 		if (idle_cpu(cpu))
diff --git a/lib/cpumask.c b/lib/cpumask.c
index 81dedaa..4731a08 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -43,6 +43,38 @@ int cpumask_any_but(const struct cpumask *mask, unsigned int cpu)
 }
 EXPORT_SYMBOL(cpumask_any_but);
 
+/**
+ * cpumask_next_wrap - helper to implement for_each_cpu_wrap
+ * @n: the cpu prior to the place to search
+ * @mask: the cpumask pointer
+ * @start: the start point of the iteration
+ * @wrap: assume @n crossing @start terminates the iteration
+ *
+ * Returns >= nr_cpu_ids on completion
+ *
+ * Note: the @wrap argument is required for the start condition when
+ * we cannot assume @start is set in @mask.
+ */
+int cpumask_next_wrap(int n, const struct cpumask *mask, int start, bool wrap)
+{
+	int next;
+
+again:
+	next = cpumask_next(n, mask);
+
+	if (wrap && n < start && next >= start) {
+		return nr_cpumask_bits;
+
+	} else if (next >= nr_cpumask_bits) {
+		wrap = true;
+		n = -1;
+		goto again;
+	}
+
+	return next;
+}
+EXPORT_SYMBOL(cpumask_next_wrap);
+
 /* These are not inline because of header tangles. */
 #ifdef CONFIG_CPUMASK_OFFSTACK
 /**

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

#1623777 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On Fri, Apr 14, 2017 at 01:38:13PM +0200, Peter Zijlstra wrote:
> On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
> > This patch constructs the sched groups from each CPU perspective. So, on
> > a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
> > groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
> > [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
> > apart.
> 
> Ah,.. so after drawing pictures I see what went wrong; duh :-(
> 
> An equivalent patch would be (if for_each_cpu_wrap() were exposed):
> 
> @@ -521,11 +588,11 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
>  	struct cpumask *covered = sched_domains_tmpmask;
>  	struct sd_data *sdd = sd->private;
>  	struct sched_domain *sibling;
> -	int i;
> +	int i, wrap;
>  
>  	cpumask_clear(covered);
>  
> -	for_each_cpu(i, span) {
> +	for_each_cpu_wrap(i, span, cpu, wrap) {
>  		struct cpumask *sg_span;
>  
>  		if (cpumask_test_cpu(i, covered))
> 
> 
> We need to start iterating at @cpu, not start at 0 every time.
> 
> 

OK, please have a look here:

https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=sched/core

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

#1624680 — Re: [RFC 2/3] sched/topology: fix sched groups on NUMA machines with mesh topology

On 04/14/2017 01:58 PM, Peter Zijlstra wrote:
> On Fri, Apr 14, 2017 at 01:38:13PM +0200, Peter Zijlstra wrote:
>> On Thu, Apr 13, 2017 at 10:56:08AM -0300, Lauro Ramos Venancio wrote:
>>> This patch constructs the sched groups from each CPU perspective. So, on
>>> a 4 nodes machine with ring topology, while nodes 0 and 2 keep the same
>>> groups as before [(3, 0, 1)(1, 2, 3)], nodes 1 and 3 have new groups
>>> [(0, 1, 2)(2, 3, 0)]. This allows moving tasks between any node 2-hops
>>> apart.
>> Ah,.. so after drawing pictures I see what went wrong; duh :-(
>>
>> An equivalent patch would be (if for_each_cpu_wrap() were exposed):
>>
>> @@ -521,11 +588,11 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
>>  	struct cpumask *covered = sched_domains_tmpmask;
>>  	struct sd_data *sdd = sd->private;
>>  	struct sched_domain *sibling;
>> -	int i;
>> +	int i, wrap;
>>  
>>  	cpumask_clear(covered);
>>  
>> -	for_each_cpu(i, span) {
>> +	for_each_cpu_wrap(i, span, cpu, wrap) {
>>  		struct cpumask *sg_span;
>>  
>>  		if (cpumask_test_cpu(i, covered))
>>
>>
>> We need to start iterating at @cpu, not start at 0 every time.
>>
>>
> OK, please have a look here:
>
> https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/log/?h=sched/core

Looks good, but please hold these patches while patch 3 is not applied.
Without it, the sched_group_capacity (sg->sgc) instance is not selected
correctly and we have an important performance regression in all NUMA
machines.

I will continue this discussion in the other thread.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web