sh: Optimise FDE/CIE lookup by using red-black trees

Now that the DWARF unwinder is being used to provide perf callstacks
unwinding speed is an issue. It is no longer being used in exceptional
circumstances where we don't care about runtime performance, e.g. when
panicing, so it makes sense improve performance is possible.

With this patch I saw a 42% improvement in unwind time when calling
return_address(1). Greater improvements will be seen as the number of
levels unwound increases as each unwind is now cheaper.

Note that insertion time has doubled but that's just the price we pay
for keeping the trees balanced. However, this is a one-time cost for
kernel boot/module load and so the improvements in lookup time dominate
the extra time we spend keeping the trees balanced.

Signed-off-by: Matt Fleming <matt@console-pimps.org>
Signed-off-by: Paul Mundt <lethal@linux-sh.org>

2 files changed, 23 insertions, 13 deletions

diff --git a/arch/sh/include/asm/dwarf.h b/arch/sh/include/asm/dwarf.h
index bdccbbfdc0bd..d62abd1d0c05 100644
--- a/arch/sh/include/asm/dwarf.h
+++ b/arch/sh/include/asm/dwarf.h
@@ -243,16 +243,13 @@ struct dwarf_cie {
 
         unsigned long cie_pointer;
 
-        struct list_head link;
-
         unsigned long flags;
 #define DWARF_CIE_Z_AUGMENTATION        (1 << 0)
 
-        /*
-         * 'mod' will be non-NULL if this CIE came from a module's
-         * .eh_frame section.
-         */
-        struct module *mod;
+        /* linked-list entry if this CIE is from a module */
+        struct list_head link;
+
+        struct rb_node node;
 };
 
 /**
@@ -266,13 +263,11 @@ struct dwarf_fde {
         unsigned long address_range;
         unsigned char *instructions;
         unsigned char *end;
+
+        /* linked-list entry if this FDE is from a module */
         struct list_head link;
 
-        /*
-         * 'mod' will be non-NULL if this FDE came from a module's
-         * .eh_frame section.
-         */
-        struct module *mod;
+        struct rb_node node;
 };
 
 /**
diff --git a/arch/sh/include/asm/module.h b/arch/sh/include/asm/module.h
index 068bf1659750..b7927de86f9f 100644
--- a/arch/sh/include/asm/module.h
+++ b/arch/sh/include/asm/module.h
@@ -1,7 +1,22 @@
 #ifndef _ASM_SH_MODULE_H
 #define _ASM_SH_MODULE_H
 
-#include <asm-generic/module.h>
+struct mod_arch_specific {
+#ifdef CONFIG_DWARF_UNWINDER
+        struct list_head fde_list;
+        struct list_head cie_list;
+#endif
+};
+
+#ifdef CONFIG_64BIT
+#define Elf_Shdr Elf64_Shdr
+#define Elf_Sym Elf64_Sym
+#define Elf_Ehdr Elf64_Ehdr
+#else
+#define Elf_Shdr Elf32_Shdr
+#define Elf_Sym Elf32_Sym
+#define Elf_Ehdr Elf32_Ehdr
+#endif
 
 #ifdef CONFIG_CPU_LITTLE_ENDIAN
 # ifdef CONFIG_CPU_SH2