lkml.org 
[lkml]   [2023]   [May]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH v3 3/3] genirq: Use the maple tree for IRQ descriptors management
From
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

\
 
 \ /
  Last update: 2023-05-10 18:04    [W:0.135 / U:0.796 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site