genriq/affinity: Make vectors allocation fair
v3 cover genriq/affinity: Make vectors allocation fair
Hi,
The 1st patch enhances one warning check.
The 2nd patch makes __irq_build_affinity_masks() more reliable, such as, all nodes can be covered in the spread.
The 3rd patch spread vectors on node according to the ratio of this node's CPU number to number of all remaining CPUs, then vectors assignment can become more fair. Meantime, the warning report from Jon Derrick can be fixed.
Please review & comment!
V3:
- re-order the patchset
- add helper of irq_spread_vectors_on_node()
- handle vector spread correctly in case that numvecs is > ncpus
- return -ENOMEM to API's caller
V2:
- add patch3
- start to allocate vectors from node with minimized CPU number, then every node is guaranteed to be allocated at least one vector.
- avoid cross node spread
Ming Lei (3):
genirq/affinity: Enhance warning check genirq/affinity: Improve __irq_build_affinity_masks() genirq/affinity: Spread vectors on node according to nr_cpu ratio
kernel/irq/affinity.c | 191 ++++++++++++++++++++++++++++++++++-------- 1 file changed, 158 insertions(+), 33 deletions(-)
Signature · 1 line
2.20.1
PATCH v3 1/3 genirq/affinity: Enhance warning check
The two-stage spread is done on same irq vectors, and we just need that either one stage covers all vector, not two stage work together to cover all vectors.
So enhance the warning check to make sure all vectors are spread.
--- kernel/irq/affinity.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/irq/affinity.c +1 -2
@@ -215,8 +215,7 @@ static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, npresmsk, nmsk, masks);put_online_cpus (); -if (nr_present < numvecs) -WARN_ON (nr_present + nr_others < numvecs); +WARN_ON (max (nr_present, nr_others) < numvecs);free_node_to_cpumask (node_to_cpumask);
Signature · 1 line
2.20.1
Re: [PATCH V3 1/3] genirq/affinity: Enhance warning check
Hi Ming,
Quoted 22 lines · Ming Lei
The two-stage spread is done on same irq vectors, and we just need that either one stage covers all vector, not two stage work together to cover all vectors.
So enhance the warning check to make sure all vectors are spread.
Cc Christoph Hellwig <hch at lst.de>Cc Keith Busch <kbusch at kernel.org>Cc linux-nvme at lists.infradead.org,Cc Jon Derrick <jonathan.derrick at intel.com>Cc Jens Axboe <axboe at kernel.dk>Fixes 6da4b3ab9a6 ("genirq/affinity: Add support for allocating interrupt sets")Signed-off-by Ming Lei <ming.lei at redhat.com>--- kernel/irq/affinity.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)kernel/irq/affinity.c +0
-0
kernel/irq/affinity.c static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, · line 218
Quoted 6 lines
kernel/irq/affinity.c +1
-2@@ -215,8 +215,7 @@ static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, npresmsk, nmsk, masks);put_online_cpus (); -if (nr_present < numvecs) -WARN_ON (nr_present + nr_others < numvecs); +WARN_ON (max (nr_present, nr_others) < numvecs);
I think the patch description assumes the first condition "The two-stage spread is done on same irq vectors"
/*
* Spread on non present CPUs starting from the next vector to be
* handled. If the spreading of present CPUs already exhausted the
* vector space, assign the non present CPUs to the already spread
* out vectors.
*/
if (nr_present >= numvecs)
curvec = firstvec;
But doesn't following condition imply nr_others spread is potentionally different vector set?
else
curvec = firstvec + nr_present;kernel/irq/affinity.c static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, · line 221
Quoted 3 lines
kernel/irq/affinity.c +0
-0free_node_to_cpumask (node_to_cpumask);
-------------- 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/20190813/cd319cc3/attachment.bin>
Re: [PATCH V3 1/3] genirq/affinity: Enhance warning check
Quoted 44 lines · Jonathan
Hi Ming,
Quoted 22 lines · Ming Lei
The two-stage spread is done on same irq vectors, and we just need that either one stage covers all vector, not two stage work together to cover all vectors.
So enhance the warning check to make sure all vectors are spread.
Cc Christoph Hellwig <hch at lst.de>Cc Keith Busch <kbusch at kernel.org>Cc linux-nvme at lists.infradead.org,Cc Jon Derrick <jonathan.derrick at intel.com>Cc Jens Axboe <axboe at kernel.dk>Fixes 6da4b3ab9a6 ("genirq/affinity: Add support for allocating interrupt sets")Signed-off-by Ming Lei <ming.lei at redhat.com>--- kernel/irq/affinity.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)kernel/irq/affinity.c +0
-0kernel/irq/affinity.c static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, · line 218
Quoted 6 lines
kernel/irq/affinity.c +1
-2@@ -215,8 +215,7 @@ static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, npresmsk, nmsk, masks);put_online_cpus (); -if (nr_present < numvecs) -WARN_ON (nr_present + nr_others < numvecs); +WARN_ON (max (nr_present, nr_others) < numvecs);I think the patch description assumes the first condition "The two-stage spread is done on same irq vectors"
/*
* Spread on non present CPUs starting from the next vector to be
* handled. If the spreading of present CPUs already exhausted the
* vector space, assign the non present CPUs to the already spread
* out vectors.
*/
if (nr_present>= numvecs)
curvec = firstvec;
Quoted 6 lines
But doesn't following condition imply
nr_othersspread is potentionally different vector set?else curvec = firstvec + nr_present;
Most times, __irq_build_affinity_masks() returns numvecs.
However, each stage may expose less CPU number than num_vecs, then less vectors than 'numvecs' can be spread.
So this patch is actually wrong.
Thank,
Ming
PATCH v3 2/3 genirq/affinity: Improve __irq_build_affinity_masks()
In reply to Ming LeiOne invariant of __irq_build_affinity_masks() is that all CPUs in the specified masks( cpu_mask AND node_to_cpumask for each node) should be covered during the spread. Even though all requested vectors have been reached, we still need to spread vectors among remained CPUs. The similar policy has been taken in case of 'numvecs <= nodes' already:
So remove the following check inside the loop:
if (done >= numvecs) break;
Meantime assign at least 1 vector for remained nodes if 'numvecs' vectors have been handled already.
Also, if the specified cpumask for one numa node is empty, simply not spread vectors on this node.
--- kernel/irq/affinity.c | 26 ++++++++++++++++++-------- 1 file changed, 18 insertions(+), 8 deletions(-)
kernel/irq/affinity.c +18 -8
@@ -129,14 +129,26 @@ 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; -/* 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); +if (!ncpus) +continue ; + +/* +* Calculate the number of cpus per vector +* +* Spread the vectors evenly per node. If the requested +* vector number has been reached, simply allocate one +* vector for each remaining node so that all nodes can +* be covered +*/ +if (numvecs > done) + vecs_per_node =max_t (unsigned, + (numvecs - done) / nodes,1 ); +else + vecs_per_node =1 ; + vecs_to_assign =min (vecs_per_node, ncpus);/* Account for rounding errors */
@@ -156,13 +168,11 @@ static int __irq_build_affinity_masks(unsigned int startvec, } done += v; -if (done >= numvecs) -break ;if (curvec >= last_affv) curvec = firstvec; --nodes; } -return done; +return done < numvecs ? done : numvecs; }/*
Signature · 1 line
2.20.1
PATCH v3 3/3 genirq/affinity: Spread vectors on node according to nr_cpu ratio
In reply to Ming LeiNow __irq_build_affinity_masks() spreads vectors evenly per node, and all vectors may not be spread in case that each numa node has different CPU number, then the following warning in irq_build_affinity_masks() can be triggered:
if (nr_present < numvecs) WARN_ON(nr_present + nr_others < numvecs);
Improve current spreading algorithm by assigning vectors according to the ratio of node's nr_cpu to nr_remaining_cpus, meantime running the assignment from smaller nodes to bigger nodes to guarantee that every active node gets allocated at least one vector, then we can avoid cross-node spread.
Meantime the reported warning can be fixed.
Another big goodness is that the spread approach becomes more fair if node has different CPU number.
For example, on the following machine:
[root at ktest-01 ~]# lscpu ... CPU(s): 16 On-line CPU(s) list: 0-15 Thread(s) per core: 1 Core(s) per socket: 8 Socket(s): 2 NUMA node(s): 2 ... NUMA node0 CPU(s): 0,1,3,5-9,11,13-15 NUMA node1 CPU(s): 2,4,10,12
When driver requests to allocate 8 vectors, the following spread can be got:
irq 31, cpu list 2,4 irq 32, cpu list 10,12 irq 33, cpu list 0-1 irq 34, cpu list 3,5 irq 35, cpu list 6-7 irq 36, cpu list 8-9 irq 37, cpu list 11,13 irq 38, cpu list 14-15
Without this patch, kernel warning is triggered on above situation, and allocation result was supposed to be 4 vectors for each node.
--- kernel/irq/affinity.c | 196 +++++++++++++++++++++++++++++++++--------- 1 file changed, 156 insertions(+), 40 deletions(-)
kernel/irq/affinity.c +156 -40
@@ -7,6 +7,7 @@#include <linux/kernel.h> #include <linux/slab.h> #include <linux/cpu.h> +#include <linux/sort.h> static void irq_spread_init_one (struct cpumask *irqmsk,struct cpumask *nmsk,unsigned int cpus_per_vec)
@@ -94,6 +95,127 @@ static int get_nodes_in_cpumask(cpumask_var_t *node_to_cpumask,return nodes; } +struct node_nr_vectors { +unsigned n; + +union { +unsigned nvectors; +unsigned ncpus; + }; +}; + +static int ncpus_cmp_func (const void *l,const void *r) +{ +const struct node_nr_vectors *ln = l; +const struct node_nr_vectors *rn = r; + +return ln->ncpus - rn->ncpus; +} + +static void alloc_nodes_vectors (unsigned int numvecs, +const cpumask_var_t *node_to_cpumask, +const struct cpumask *cpu_mask, +const nodemask_t nodemsk, +struct cpumask *nmsk, +struct node_nr_vectors *node_vectors) +{ +unsigned remaining_ncpus =0 ; +unsigned n; + +for (n =0 ; n < nr_node_ids; n++) { + node_vectors[n].n = n; + node_vectors[n].ncpus =UINT_MAX ; + } + +for_each_node_mask (n, nodemsk) { +unsigned ncpus; + +cpumask_and (nmsk, cpu_mask, node_to_cpumask[n]); + ncpus =cpumask_weight (nmsk); + +if (!ncpus) +continue ; + remaining_ncpus += ncpus; + node_vectors[n].ncpus = ncpus; + } + +sort (node_vectors, nr_node_ids,sizeof (node_vectors[0 ]), + ncpus_cmp_func,NULL ); + +/* +* Allocate vectors for each node according to the ratio of this +* node's nr_cpus to remaining un-assigned ncpus. 'numvecs' is +* bigger than number of active numa nodes. Always start the +* allocation from the node with minimized nr_cpus. +* +* This way guarantees that each active node gets allocated at +* least one vector, and the theory is simple: over-allocation +* is only done when this node is assigned by one vector, so +* other nodes will be allocated >= 1 vector, since 'numvecs' is +* bigger than number of numa nodes. +*/ +for (n =0 ; n < nr_node_ids; n++) { +unsigned nvectors, ncpus; + +if (node_vectors[n].ncpus ==UINT_MAX ) +continue ; + +WARN_ON_ONCE (numvecs ==0 ); + + ncpus = node_vectors[n].ncpus; + nvectors =max_t (unsigned,1 , + numvecs * ncpus / remaining_ncpus); + + node_vectors[n].nvectors = nvectors; + remaining_ncpus -= ncpus; + numvecs -= nvectors; + } +} + +/** +* irq_spread_vectors_on_node - Spread vectors on one node +* @startvec: The 1st vector to be spread +* @numvecs: The number of vectors to be spread +* @nmsk: The cpumask of this node +* @masks: The cpumask array for storing vector affinity +*/ +static void irq_spread_vectors_on_node (unsigned startvec,unsigned numvecs, +struct cpumask *nmsk, +struct irq_affinity_desc *masks) +{ +unsigned ncpus =cpumask_weight (nmsk); + +while (numvecs >0 ) { +unsigned v, vecs_to_assign, extra_vecs; +unsigned curvec = startvec; + +/* +* alloc_nodes_vectors() is intelligent enough to +* allocate vectors for each node. If the allocated +* vectors is bigger than node's CPU number because +* of rounddown, wraps to the first vector for this +* node, then cross-node spread can be avoided. +*/ + vecs_to_assign =min (numvecs, ncpus); + +/* Account for rounding errors */ + extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign); + +for (v =0 ; v < vecs_to_assign; v++, curvec++) { +unsigned cpus_per_vec = ncpus / vecs_to_assign; + +/* Account for extra vectors to compensate rounding errors */ +if (extra_vecs) { + cpus_per_vec++; + --extra_vecs; + } +irq_spread_init_one (&masks[curvec].mask, nmsk, + cpus_per_vec); + } + numvecs -= vecs_to_assign; + } +} + static int __irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, unsigned int firstvec,
@@ -102,10 +224,11 @@ static int __irq_build_affinity_masks(unsigned int startvec,struct cpumask *nmsk, struct irq_affinity_desc *masks) { - unsigned int n, nodes, cpus_per_vec, extra_vecs, done = 0; + unsigned int i, n, nodes, done = 0;unsigned int last_affv = firstvec + numvecs;unsigned int curvec = startvec;nodemask_t nodemsk =NODE_MASK_NONE ; +struct node_nr_vectors *node_vectors;if (!cpumask_weight (cpu_mask))return 0 ;
@@ -126,52 +249,36 @@ static int __irq_build_affinity_masks(unsigned int startvec,return numvecs; } -for_each_node_mask (n, nodemsk) { -unsigned int ncpus, v, vecs_to_assign, vecs_per_node; + node_vectors =kcalloc (nr_node_ids, +sizeof (struct node_nr_vectors ), +GFP_KERNEL ); +if (!node_vectors) +return -ENOMEM ; + +alloc_nodes_vectors (numvecs, node_to_cpumask, cpu_mask, + nodemsk, nmsk, node_vectors); + +for (i =0 ; i < nr_node_ids; i++) { +unsigned int ncpus; +struct node_nr_vectors *nv = &node_vectors[i]; + +if (nv->nvectors ==UINT_MAX ) +continue ;/* Get the cpus on this node which are in the mask */ -cpumask_and (nmsk, cpu_mask, node_to_cpumask[n]); +cpumask_and (nmsk, cpu_mask, node_to_cpumask[nv->n]); ncpus =cpumask_weight (nmsk);if (!ncpus)continue ; -/* -* Calculate the number of cpus per vector -* -* Spread the vectors evenly per node. If the requested -* vector number has been reached, simply allocate one -* vector for each remaining node so that all nodes can -* be covered -*/ -if (numvecs > done) - vecs_per_node =max_t (unsigned, - (numvecs - done) / nodes,1 ); -else - vecs_per_node =1 ; - - vecs_to_assign =min (vecs_per_node, ncpus); - -/* Account for rounding errors */ - extra_vecs = ncpus - vecs_to_assign * (ncpus / vecs_to_assign); - -for (v =0 ; curvec < last_affv && v < vecs_to_assign; - curvec++, v++) { - cpus_per_vec = ncpus / vecs_to_assign; +WARN_ON_ONCE (nv->nvectors ==UINT_MAX ); +WARN_ON_ONCE (curvec + nv->nvectors > last_affv); +irq_spread_vectors_on_node (curvec, nv->nvectors, nmsk, masks); -/* Account for extra vectors to compensate rounding errors */ -if (extra_vecs) { - cpus_per_vec++; - --extra_vecs; - } -irq_spread_init_one (&masks[curvec].mask, nmsk, - cpus_per_vec); - } - - done += v; -if (curvec >= last_affv) - curvec = firstvec; - --nodes; + curvec += nv->nvectors; + done += nv->nvectors; } +kfree (node_vectors);return done < numvecs ? done : numvecs; }
@@ -208,6 +315,10 @@ static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, nr_present =__irq_build_affinity_masks (curvec, numvecs, firstvec, node_to_cpumask, cpu_present_mask, nmsk, masks); +if (nr_present <0 ) { + ret = nr_present; + goto fail_build_affinity; + }/* * Spread on non present CPUs starting from the next vector to be
@@ -223,9 +334,14 @@ static int irq_build_affinity_masks(unsigned int startvec, unsigned int numvecs, nr_others =__irq_build_affinity_masks (curvec, numvecs, firstvec, node_to_cpumask, npresmsk, nmsk, masks); +if (nr_others <0 ) + ret = nr_others; + + fail_build_affinity:put_online_cpus (); -WARN_ON (max (nr_present, nr_others) < numvecs); +WARN_ON (min (nr_present, nr_others) >=0 && +max (nr_present, nr_others) < numvecs);free_node_to_cpumask (node_to_cpumask);
Signature · 1 line
2.20.1
Re: [PATCH V3 3/3] genirq/affinity: Spread vectors on node according to nr_cpu ratio
Hi,
Quoted 7 lines · Ming Lei
Now
__irq_build_affinity_masks()spreads vectors evenly per node, and all vectors may not be spread in case that each numa node has different CPU number, then the following warning inirq_build_affinity_masks()can be triggered:if (nr_present < numvecs) WARN_ON(nr_present + nr_others < numvecs);
Is this the warning which is changed in patch #1?
Thanks,
Daniel