Messages in this thread | | | Date | Wed, 10 May 2023 11:02:37 -0500 | Subject | Re: [PATCH v3 3/3] genirq: Use the maple tree for IRQ descriptors management | From | Shanker Donthineni <> |
| |
Hi Thomas,
On 4/10/23 10:57, Shanker Donthineni wrote: > The current implementation uses a static bitmap and a radix tree > to manage IRQ allocation and irq_desc pointer store respectively. > However, the size of the bitmap is constrained by the build time > macro MAX_SPARSE_IRQS, which may not be sufficient to support the > high-end servers, particularly those with GICv4.1 hardware, which > require a large interrupt space to cover LPIs and vSGIs. > > The maple tree is a highly efficient data structure for storing > non-overlapping ranges and can handle a large number of entries, > up to ULONG_MAX. It can be utilized for both storing interrupt > descriptors and identifying available free spaces. > > The interrupt descriptors management can be simplified by switching > to a maple tree data structure, which offers greater flexibility > and scalability. To support modern servers, the maximum number of > IRQs has been increased to INT_MAX, which provides a more adequate > value than the previous limit of NR_IRQS+8192. > > Signed-off-by: Shanker Donthineni <sdonthineni@nvidia.com> > --- > kernel/irq/internals.h | 2 +- > kernel/irq/irqdesc.c | 54 +++++++++++++++++++++++------------------- > 2 files changed, 31 insertions(+), 25 deletions(-) > > diff --git a/kernel/irq/internals.h b/kernel/irq/internals.h > index f3f2090dd2de..7bdb7507efb0 100644 > --- a/kernel/irq/internals.h > +++ b/kernel/irq/internals.h > @@ -12,7 +12,7 @@ > #include <linux/sched/clock.h> > > #ifdef CONFIG_SPARSE_IRQ > -# define MAX_SPARSE_IRQS (NR_IRQS + 8196) > +# define MAX_SPARSE_IRQS INT_MAX > #else > # define MAX_SPARSE_IRQS NR_IRQS > #endif > diff --git a/kernel/irq/irqdesc.c b/kernel/irq/irqdesc.c > index 9a71fc6f2c5f..d6d8120ffd56 100644 > --- a/kernel/irq/irqdesc.c > +++ b/kernel/irq/irqdesc.c > @@ -12,8 +12,7 @@ > #include <linux/export.h> > #include <linux/interrupt.h> > #include <linux/kernel_stat.h> > -#include <linux/radix-tree.h> > -#include <linux/bitmap.h> > +#include <linux/maple_tree.h> > #include <linux/irqdomain.h> > #include <linux/sysfs.h> > > @@ -131,17 +130,38 @@ int nr_irqs = NR_IRQS; > EXPORT_SYMBOL_GPL(nr_irqs); > > static DEFINE_MUTEX(sparse_irq_lock); > -static DECLARE_BITMAP(allocated_irqs, MAX_SPARSE_IRQS); > +static struct maple_tree sparse_irqs = MTREE_INIT_EXT(sparse_irqs, > + MT_FLAGS_ALLOC_RANGE | > + MT_FLAGS_LOCK_EXTERN | > + MT_FLAGS_USE_RCU, > + sparse_irq_lock); > > static int irq_find_free_area(unsigned int from, unsigned int cnt) > { > - return bitmap_find_next_zero_area(allocated_irqs, MAX_SPARSE_IRQS, > - from, cnt, 0); > + MA_STATE(mas, &sparse_irqs, 0, 0); > + > + if (mas_empty_area(&mas, from, MAX_SPARSE_IRQS, cnt)) > + return -ENOSPC; > + return mas.index; > } > > static unsigned int irq_find_next_irq(unsigned int offset) > { > - return find_next_bit(allocated_irqs, nr_irqs, offset); > + struct irq_desc *desc = mt_next(&sparse_irqs, offset, nr_irqs); > + > + return desc ? irq_desc_get_irq(desc) : nr_irqs; > +} > +
Based on the comments of mt_find(), seems it is the right function to use for finding the next entry.
static unsigned int irq_find_next_irq(unsigned int offset) { struct irq_desc *desc = mt_find(&sparse_irqs, offset, nr_irqs);
return desc ? irq_desc_get_irq(desc) : nr_irqs; }
-Shanker
| |