sh: intc: optimize intc IRQ lookup
Paul Mundt [Tue, 24 Jan 2012 08:41:55 +0000 (17:41 +0900)]
This ensures that the sense/prio lists are sorted at registration time,
enabling us to use a simple binary search for an optimized lookup
(something that had been on the TODO for some time).

Signed-off-by: Paul Mundt <lethal@linux-sh.org>

drivers/sh/intc/chip.c
drivers/sh/intc/core.c
drivers/sh/intc/internals.h

index db10adf..012df26 100644 (file)
@@ -2,13 +2,14 @@
  * IRQ chip definitions for INTC IRQs.
  *
  * Copyright (C) 2007, 2008 Magnus Damm
- * Copyright (C) 2009, 2010 Paul Mundt
+ * Copyright (C) 2009 - 2012 Paul Mundt
  *
  * This file is subject to the terms and conditions of the GNU General Public
  * License.  See the file "COPYING" in the main directory of this archive
  * for more details.
  */
 #include <linux/cpumask.h>
+#include <linux/bsearch.h>
 #include <linux/io.h>
 #include "internals.h"
 
@@ -117,28 +118,12 @@ static struct intc_handle_int *intc_find_irq(struct intc_handle_int *hp,
                                             unsigned int nr_hp,
                                             unsigned int irq)
 {
-       int i;
-
-       /*
-        * this doesn't scale well, but...
-        *
-        * this function should only be used for cerain uncommon
-        * operations such as intc_set_priority() and intc_set_type()
-        * and in those rare cases performance doesn't matter that much.
-        * keeping the memory footprint low is more important.
-        *
-        * one rather simple way to speed this up and still keep the
-        * memory footprint down is to make sure the array is sorted
-        * and then perform a bisect to lookup the irq.
-        */
-       for (i = 0; i < nr_hp; i++) {
-               if ((hp + i)->irq != irq)
-                       continue;
+       struct intc_handle_int key;
 
-               return hp + i;
-       }
+       key.irq = irq;
+       key.handle = 0;
 
-       return NULL;
+       return bsearch(&key, hp, nr_hp, sizeof(*hp), intc_handle_int_cmp);
 }
 
 int intc_set_priority(unsigned int irq, unsigned int prio)
index c64690d..8e1fcd5 100644 (file)
@@ -2,7 +2,7 @@
  * Shared interrupt handling code for IPR and INTC2 types of IRQs.
  *
  * Copyright (C) 2007, 2008 Magnus Damm
- * Copyright (C) 2009, 2010 Paul Mundt
+ * Copyright (C) 2009 - 2012 Paul Mundt
  *
  * Based on intc2.c and ipr.c
  *
@@ -31,6 +31,7 @@
 #include <linux/spinlock.h>
 #include <linux/radix-tree.h>
 #include <linux/export.h>
+#include <linux/sort.h>
 #include "internals.h"
 
 LIST_HEAD(intc_list);
@@ -267,6 +268,9 @@ int __init register_intc_controller(struct intc_desc *desc)
                        k += save_reg(d, k, hw->prio_regs[i].set_reg, smp);
                        k += save_reg(d, k, hw->prio_regs[i].clr_reg, smp);
                }
+
+               sort(d->prio, hw->nr_prio_regs, sizeof(*d->prio),
+                    intc_handle_int_cmp, NULL);
        }
 
        if (hw->sense_regs) {
@@ -277,6 +281,9 @@ int __init register_intc_controller(struct intc_desc *desc)
 
                for (i = 0; i < hw->nr_sense_regs; i++)
                        k += save_reg(d, k, hw->sense_regs[i].reg, 0);
+
+               sort(d->sense, hw->nr_sense_regs, sizeof(*d->sense),
+                    intc_handle_int_cmp, NULL);
        }
 
        if (hw->subgroups)
index 422b72d..f034a97 100644 (file)
@@ -108,6 +108,14 @@ static inline void activate_irq(int irq)
 #endif
 }
 
+static inline int intc_handle_int_cmp(const void *a, const void *b)
+{
+       const struct intc_handle_int *_a = a;
+       const struct intc_handle_int *_b = b;
+
+       return _a->irq - _b->irq;
+}
+
 /* access.c */
 extern unsigned long
 (*intc_reg_fns[])(unsigned long addr, unsigned long h, unsigned long data);