Skip to contentSkip to conversation

genirq/affinity: report extra vectors on uneven nodes

PATCH In review Jon Derrick 4 participants 6 messages Aug 7, 2019 – Aug 9, 2019

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 genirq/affinity: report extra vectors on uneven nodes

The current irq spreading algorithm spreads vectors amongst cpus evenly per node. If a node has more cpus than another node, the extra vectors being spread may not be reported back to the caller.

This is most apparent with the NVMe driver and nr_cpus < vectors, where the underreporting results in the caller's WARN being triggered:

irq_build_affinity_masks()
...

	if (nr_present < numvecs)
		WARN_ON(nr_present + nr_others < numvecs);
Signed-off-by Jon Derrick <jonathan.derrick at intel.com>
---
 kernel/irq/affinity.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/irq/affinity.c +5 -2
index 4352b08ae48d..9beafb8c7e92 100644
@@ -127,7 +127,8 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 	}
 
 	for_each_node_mask(n, nodemsk) {
-		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
+		unsigned int ncpus, v, vecs_to_assign, total_vecs_to_assign,
+			vecs_per_node;
 
 		/* Spread the vectors per node */
 		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
@@ -141,14 +142,16 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 		/* Account for rounding errors */
 		extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign);
+		total_vecs_to_assign = vecs_to_assign + extra_vecs;
 
-		for (v = 0; curvec < last_affv && v < vecs_to_assign;
+		for (v = 0; curvec < last_affv && v < total_vecs_to_assign;
 		     curvec++, v++) {
 			cpus_per_vec = ncpus / vecs_to_assign;
 
 			/* Account for extra vectors to compensate rounding errors */
 			if (extra_vecs) {
 				cpus_per_vec++;
+				v++;
 				--extra_vecs;
 			}
 			irq_spread_init_one(&masks[curvec].mask, nmsk,
Signature · 1 line
2.20.1
#1 lore raw

On Wed, 7 Aug 2019, Jon Derrick wrote:

Cc+: Ming, Christoph.

Left context for reference.

Quoted 53 lines

The current irq spreading algorithm spreads vectors amongst cpus evenly per node. If a node has more cpus than another node, the extra vectors being spread may not be reported back to the caller.

This is most apparent with the NVMe driver and nr_cpus < vectors, where the underreporting results in the caller's WARN being triggered:

irq_build_affinity_masks()
...

	if (nr_present < numvecs)
		WARN_ON(nr_present + nr_others < numvecs);
Signed-off-by Jon Derrick <jonathan.derrick at intel.com>
---
 kernel/irq/affinity.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/irq/affinity.c +5 -2
index 4352b08ae48d..9beafb8c7e92 100644
@@ -127,7 +127,8 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 	}
 
 	for_each_node_mask(n, nodemsk) {
-		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
+		unsigned int ncpus, v, vecs_to_assign, total_vecs_to_assign,
+			vecs_per_node;
 
 		/* Spread the vectors per node */
 		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
@@ -141,14 +142,16 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 		/* Account for rounding errors */
 		extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign);
+		total_vecs_to_assign = vecs_to_assign + extra_vecs;
 
-		for (v = 0; curvec < last_affv && v < vecs_to_assign;
+		for (v = 0; curvec < last_affv && v < total_vecs_to_assign;
 		     curvec++, v++) {
 			cpus_per_vec = ncpus / vecs_to_assign;
 
 			/* Account for extra vectors to compensate rounding errors */
 			if (extra_vecs) {
 				cpus_per_vec++;
+				v++;
 				--extra_vecs;
 			}
 			irq_spread_init_one(&masks[curvec].mask, nmsk,
Signature · 1 line
2.20.1
maintainer
#2 lore raw
Quoted 43 lines · Thomas Gleixner
Quoted 42 lines · Jon Derrick

The current irq spreading algorithm spreads vectors amongst cpus evenly per node. If a node has more cpus than another node, the extra vectors being spread may not be reported back to the caller.

This is most apparent with the NVMe driver and nr_cpus < vectors, where the underreporting results in the caller's WARN being triggered:

irq_build_affinity_masks()
...

	if (nr_present < numvecs)
		WARN_ON(nr_present + nr_others < numvecs);
Signed-off-by Jon Derrick <jonathan.derrick at intel.com>
---
 kernel/irq/affinity.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/irq/affinity.c +4 -2
index 4352b08ae48d..9beafb8c7e92 100644
@@ -127,7 +127,8 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 	}
 
 	for_each_node_mask(n, nodemsk) {
-		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
+		unsigned int ncpus, v, vecs_to_assign, total_vecs_to_assign,
+			vecs_per_node;
 
 		/* Spread the vectors per node */
 		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
@@ -141,14 +142,16 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 		/* Account for rounding errors */
 		extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign);
+		total_vecs_to_assign = vecs_to_assign + extra_vecs;
 
-		for (v = 0; curvec < last_affv && v < vecs_to_assign;
+		for (v = 0; curvec < last_affv && v < total_vecs_to_assign;
 		     curvec++, v++) {
 			cpus_per_vec = ncpus / vecs_to_assign;
 
Quoted 8 lines

kernel/irq/affinity.c static int __irq_build_affinity_masks(unsigned int startvec, · line 157

Quoted 8 lines
kernel/irq/affinity.c +1 -0
 			/* Account for extra vectors to compensate rounding errors */
 			if (extra_vecs) {
 				cpus_per_vec++;
+				v++;
 				--extra_vecs;
 			}
 			irq_spread_init_one(&masks[curvec].mask, nmsk,

This looks like it will break the spread to non-present CPUs since it's not accurately reporting how many vectors were assigned for the present spread.

I think the real problem is the spread's vecs_per_node doesn't account which nodes contribute more CPUs than others. For example:

Node 0 has 32 CPUs
Node 1 has 8 CPUs
Assign 32 vectors

The current algorithm assigns 16 vectors to node 0 because vecs_per_node is calculated as 32 vectors / 2 nodes on the first iteration. The subsequent iteration for node 1 gets 8 vectors because it has only 8 CPUs, leaving 8 vectors unassigned.

A more fair spread would give node 0 the remaining 8 vectors. This optimization, however, is a bit more complex than the current algorithm, which is probably why it wasn't done, so I think the warning should just be removed.

#3 lore raw
Quoted 69 lines · Keith Busch
Quoted 43 lines · Thomas Gleixner
Quoted 42 lines · Jon Derrick

The current irq spreading algorithm spreads vectors amongst cpus evenly per node. If a node has more cpus than another node, the extra vectors being spread may not be reported back to the caller.

This is most apparent with the NVMe driver and nr_cpus < vectors, where the underreporting results in the caller's WARN being triggered:

irq_build_affinity_masks()
...

	if (nr_present < numvecs)
		WARN_ON(nr_present + nr_others < numvecs);
Signed-off-by Jon Derrick <jonathan.derrick at intel.com>
---
 kernel/irq/affinity.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/irq/affinity.c +4 -2
index 4352b08ae48d..9beafb8c7e92 100644
@@ -127,7 +127,8 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 	}
 
 	for_each_node_mask(n, nodemsk) {
-		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
+		unsigned int ncpus, v, vecs_to_assign, total_vecs_to_assign,
+			vecs_per_node;
 
 		/* Spread the vectors per node */
 		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
@@ -141,14 +142,16 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 		/* Account for rounding errors */
 		extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign);
+		total_vecs_to_assign = vecs_to_assign + extra_vecs;
 
-		for (v = 0; curvec < last_affv && v < vecs_to_assign;
+		for (v = 0; curvec < last_affv && v < total_vecs_to_assign;
 		     curvec++, v++) {
 			cpus_per_vec = ncpus / vecs_to_assign;
 
Quoted 8 lines

kernel/irq/affinity.c static int __irq_build_affinity_masks(unsigned int startvec, · line 157

Quoted 8 lines
kernel/irq/affinity.c +1 -0
 			/* Account for extra vectors to compensate rounding errors */
 			if (extra_vecs) {
 				cpus_per_vec++;
+				v++;
 				--extra_vecs;
 			}
 			irq_spread_init_one(&masks[curvec].mask, nmsk,

This looks like it will break the spread to non-present CPUs since it's not accurately reporting how many vectors were assigned for the present spread.

I think the real problem is the spread's vecs_per_node doesn't account which nodes contribute more CPUs than others. For example:

Node 0 has 32 CPUs
Node 1 has 8 CPUs
Assign 32 vectors

The current algorithm assigns 16 vectors to node 0 because vecs_per_node is calculated as 32 vectors / 2 nodes on the first iteration. The subsequent iteration for node 1 gets 8 vectors because it has only 8 CPUs, leaving 8 vectors unassigned.

Quoted 4 lines

A more fair spread would give node 0 the remaining 8 vectors. This optimization, however, is a bit more complex than the current algorithm, which is probably why it wasn't done, so I think the warning should just be removed.

It does get a bit complex for the rare scenario in this case
Maybe just an informational warning rather than a stackdumping warning -------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 3278 bytes
Desc: not available
URL: <http://lists.infradead.org/pipermail/linux-nvme/attachments/20190808/79da8b7e/attachment.bin>

maintainer
#4 lore raw
Quoted 14 lines · Jonathan
Quoted 13 lines · Keith Busch

I think the real problem is the spread's vecs_per_node doesn't account which nodes contribute more CPUs than others. For example:

Node 0 has 32 CPUs
Node 1 has 8 CPUs
Assign 32 vectors

The current algorithm assigns 16 vectors to node 0 because vecs_per_node is calculated as 32 vectors / 2 nodes on the first iteration. The subsequent iteration for node 1 gets 8 vectors because it has only 8 CPUs, leaving 8 vectors unassigned.

Quoted 7 lines
Quoted 4 lines

A more fair spread would give node 0 the remaining 8 vectors. This optimization, however, is a bit more complex than the current algorithm, which is probably why it wasn't done, so I think the warning should just be removed.

It does get a bit complex for the rare scenario in this case Maybe just an informational warning rather than a stackdumping warning

I think the easiest way to ensure all vectors are assigned is iterate the nodes in a sorted order from fewest CPUs to most. That should fix the warning, though it may not have the best possible assignment ratio (but better than what we're currently doing).

Unfortunately the kernel's sort() doesn't take a 'void *priv' for the compare callback, so we wouldn't have all the information needed to weigh each node, but maybe we can fix that if there's agreement to iterate the nodes this way.

#5 lore raw
In reply to Keith Busch
Quoted 69 lines · Keith Busch
Quoted 43 lines · Thomas Gleixner
Quoted 42 lines · Jon Derrick

The current irq spreading algorithm spreads vectors amongst cpus evenly per node. If a node has more cpus than another node, the extra vectors being spread may not be reported back to the caller.

This is most apparent with the NVMe driver and nr_cpus < vectors, where the underreporting results in the caller's WARN being triggered:

irq_build_affinity_masks()
...

	if (nr_present < numvecs)
		WARN_ON(nr_present + nr_others < numvecs);
Signed-off-by Jon Derrick <jonathan.derrick at intel.com>
---
 kernel/irq/affinity.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)
kernel/irq/affinity.c +4 -2
index 4352b08ae48d..9beafb8c7e92 100644
@@ -127,7 +127,8 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 	}
 
 	for_each_node_mask(n, nodemsk) {
-		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
+		unsigned int ncpus, v, vecs_to_assign, total_vecs_to_assign,
+			vecs_per_node;
 
 		/* Spread the vectors per node */
 		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
@@ -141,14 +142,16 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 		/* Account for rounding errors */
 		extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign);
+		total_vecs_to_assign = vecs_to_assign + extra_vecs;
 
-		for (v = 0; curvec < last_affv && v < vecs_to_assign;
+		for (v = 0; curvec < last_affv && v < total_vecs_to_assign;
 		     curvec++, v++) {
 			cpus_per_vec = ncpus / vecs_to_assign;
 
Quoted 8 lines

kernel/irq/affinity.c static int __irq_build_affinity_masks(unsigned int startvec, · line 157

Quoted 8 lines
kernel/irq/affinity.c +1 -0
 			/* Account for extra vectors to compensate rounding errors */
 			if (extra_vecs) {
 				cpus_per_vec++;
+				v++;
 				--extra_vecs;
 			}
 			irq_spread_init_one(&masks[curvec].mask, nmsk,

This looks like it will break the spread to non-present CPUs since it's not accurately reporting how many vectors were assigned for the present spread.

I think the real problem is the spread's vecs_per_node doesn't account which nodes contribute more CPUs than others. For example:

Node 0 has 32 CPUs
Node 1 has 8 CPUs
Assign 32 vectors

The current algorithm assigns 16 vectors to node 0 because vecs_per_node is calculated as 32 vectors / 2 nodes on the first iteration. The subsequent iteration for node 1 gets 8 vectors because it has only 8 CPUs, leaving 8 vectors unassigned.

Quoted 4 lines

A more fair spread would give node 0 the remaining 8 vectors. This optimization, however, is a bit more complex than the current algorithm, which is probably why it wasn't done, so I think the warning should just be removed.

Another policy is to assign vectors among nodes according to the following ratio:

ncpus in this node / total ncpus in un-assigned nodes

I have tried the following patch, looks it works fine:

kernel/irq/affinity.c +35 -4
index 6fef48033f96..a598f20701a3 100644
@@ -94,6 +94,28 @@ static int get_nodes_in_cpumask(cpumask_var_t *node_to_cpumask,
 	return nodes;
 }
 
+static int nodes_cpus(unsigned start_node, const nodemask_t nodemsk,
+		const cpumask_var_t *node_to_cpumask,
+		const struct cpumask *cpu_mask, struct cpumask *nmsk)
+{
+	unsigned n, ncpus, total_cpus = 0;
+
+	for_each_node_mask(n, nodemsk) {
+		if (n < start_node)
+			continue;
+
+		/* Get the cpus on this node which are in the mask */
+		cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]);
+
+		/* Calculate the number of cpus per vector */
+		ncpus = cpumask_weight(nmsk);
+
+		total_cpus += ncpus;
+	}
+
+	return total_cpus;
+}
+
 static int __irq_build_affinity_masks(unsigned int startvec,
 				      unsigned int numvecs,
 				      unsigned int firstvec,
@@ -128,15 +150,25 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 
 	for_each_node_mask(n, nodemsk) {
 		unsigned int ncpus, v, vecs_to_assign, vecs_per_node;
-
-		/* Spread the vectors per node */
-		vecs_per_node = (numvecs - (curvec - firstvec)) / nodes;
+		unsigned int ncpus_left = nodes_cpus(n, nodemsk,
+				node_to_cpumask, cpu_mask, nmsk);
 
 		/* Get the cpus on this node which are in the mask */
 		cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]);
 
 		/* Calculate the number of cpus per vector */
 		ncpus = cpumask_weight(nmsk);
+
+		/*
+		 * Spread the vectors per node, and node with more CPUs will be
+		 * assigned to more vectors
+		 */
+		vecs_per_node = (numvecs - (curvec - firstvec)) * ncpus / ncpus_left;
+
+		/* at least assign one vector for this node */
+		if (!vecs_per_node)
+			vecs_per_node = 1;
+
 		vecs_to_assign = min(vecs_per_node, ncpus);
 
 		/* Account for rounding errors */
@@ -160,7 +192,6 @@ static int __irq_build_affinity_masks(unsigned int startvec,
 			break;
 		if (curvec >= last_affv)
 			curvec = firstvec;
-		--nodes;
 	}
 	return done;
 }

thanks,
Ming