lkml.org 
[lkml]   [2023]   [Jan]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 5/5] genirq: Use the maple tree for IRQ descriptors management
    Date
    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 IRQD and
    identifying available free spaces.

    The IRQD 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 | 51 ++++++++++++++++++++++++------------------
    2 files changed, 30 insertions(+), 23 deletions(-)

    diff --git a/kernel/irq/internals.h b/kernel/irq/internals.h
    index 5d741b0e7d5e..e35de737802c 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 247a0718d028..06be5f924a7c 100644
    --- a/kernel/irq/irqdesc.c
    +++ b/kernel/irq/irqdesc.c
    @@ -15,6 +15,7 @@
    #include <linux/radix-tree.h>
    #include <linux/bitmap.h>
    #include <linux/irqdomain.h>
    +#include <linux/maple_tree.h>
    #include <linux/sysfs.h>

    #include "internals.h"
    @@ -131,17 +132,37 @@ 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;
    +}
    +
    +static void irq_insert_desc(unsigned int irq, struct irq_desc *desc)
    +{
    + MA_STATE(mas, &sparse_irqs, irq, irq);
    + WARN_ON(mas_store_gfp(&mas, desc, GFP_KERNEL) != 0);
    +}
    +
    +static void delete_irq_desc(unsigned int irq)
    +{
    + MA_STATE(mas, &sparse_irqs, irq, irq);
    + mas_erase(&mas);
    }

    static int irq_expand_nr_irqs(unsigned int nr)
    @@ -363,26 +384,14 @@ static void irq_sysfs_del(struct irq_desc *desc) {}

    #endif /* CONFIG_SYSFS */

    -static RADIX_TREE(irq_desc_tree, GFP_KERNEL);
    -
    -static void irq_insert_desc(unsigned int irq, struct irq_desc *desc)
    -{
    - radix_tree_insert(&irq_desc_tree, irq, desc);
    -}
    -
    struct irq_desc *irq_to_desc(unsigned int irq)
    {
    - return radix_tree_lookup(&irq_desc_tree, irq);
    + return mtree_load(&sparse_irqs, irq);
    }
    #ifdef CONFIG_KVM_BOOK3S_64_HV_MODULE
    EXPORT_SYMBOL_GPL(irq_to_desc);
    #endif

    -static void delete_irq_desc(unsigned int irq)
    -{
    - radix_tree_delete(&irq_desc_tree, irq);
    -}
    -
    #ifdef CONFIG_SMP
    static void free_masks(struct irq_desc *desc)
    {
    @@ -527,7 +536,6 @@ static int alloc_descs(unsigned int start, unsigned int cnt, int node,
    irq_sysfs_add(start + i, desc);
    irq_add_debugfs_entry(start + i, desc);
    }
    - bitmap_set(allocated_irqs, start, cnt);
    return start;

    err:
    @@ -559,7 +567,6 @@ int __init early_irq_init(void)

    for (i = 0; i < initcnt; i++) {
    desc = alloc_desc(i, node, 0, NULL, NULL);
    - set_bit(i, allocated_irqs);
    irq_insert_desc(i, desc);
    }
    return arch_early_irq_init();
    @@ -613,6 +620,7 @@ static void free_desc(unsigned int irq)
    raw_spin_lock_irqsave(&desc->lock, flags);
    desc_set_defaults(irq, desc, irq_desc_get_node(desc), NULL, NULL);
    raw_spin_unlock_irqrestore(&desc->lock, flags);
    + delete_irq_desc(irq);
    }

    static inline int alloc_descs(unsigned int start, unsigned int cnt, int node,
    @@ -625,15 +633,15 @@ static inline int alloc_descs(unsigned int start, unsigned int cnt, int node,
    struct irq_desc *desc = irq_to_desc(start + i);

    desc->owner = owner;
    + irq_insert_desc(start + i, desc);
    }
    - bitmap_set(allocated_irqs, start, cnt);
    return start;
    }

    void irq_mark_irq(unsigned int irq)
    {
    mutex_lock(&sparse_irq_lock);
    - bitmap_set(allocated_irqs, irq, 1);
    + irq_insert_desc(irq, irq_descs + irq);
    mutex_unlock(&sparse_irq_lock);
    }

    @@ -777,7 +785,6 @@ void irq_free_descs(unsigned int from, unsigned int cnt)
    for (i = 0; i < cnt; i++)
    free_desc(from + i);

    - bitmap_clear(allocated_irqs, from, cnt);
    mutex_unlock(&sparse_irq_lock);
    }
    EXPORT_SYMBOL_GPL(irq_free_descs);
    --
    2.25.1
    \
     
     \ /
      Last update: 2023-03-27 00:01    [W:4.238 / U:1.588 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site