[binutils-gdb] Fix N^2 behavior in _bfd_dwarf2_find_symbol_bias

[Tom Tromey]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7

commit 3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7
Author: Tom Tromey <tromey@adacore.com>
Date:   Thu Aug 15 07:33:20 2019 -0600

    Fix N^2 behavior in _bfd_dwarf2_find_symbol_bias
    
    A customer reported a case where addr2line was very slow.  We tracked
    this down to some N^2 behavior in _bfd_dwarf2_find_symbol_bias in the
    unusual case where no function can be found.
    
    This patch fixes the bug, and reduces the runtime for a particular
    request from 127 seconds to 1 second.
    
    bfd/ChangeLog
    2019-08-19  Tom Tromey  <tromey@adacore.com>
    
    	* dwarf2.c (_bfd_dwarf2_find_symbol_bias): Create hash table
    	holding symbols.

Diff:
---
 bfd/ChangeLog |  5 +++++
 bfd/dwarf2.c  | 56 ++++++++++++++++++++++++++++++++++++++++++++++----------
 2 files changed, 51 insertions(+), 10 deletions(-)

diff --git a/bfd/ChangeLog b/bfd/ChangeLog
index 4c94113..bfaec7b 100644
--- a/bfd/ChangeLog
+++ b/bfd/ChangeLog
@@ -1,3 +1,8 @@
+2019-08-19  Tom Tromey  <tromey@adacore.com>
+
+	* dwarf2.c (_bfd_dwarf2_find_symbol_bias): Create hash table
+	holding symbols.
+
 2019-08-19  Alan Modra  <amodra@gmail.com>
 
 	* elf64-ppc.c (struct ppc64_elf_obj_tdata): Rename has_gotrel
diff --git a/bfd/dwarf2.c b/bfd/dwarf2.c
index d56244b..a8beec4 100644
--- a/bfd/dwarf2.c
+++ b/bfd/dwarf2.c
@@ -35,6 +35,7 @@
 #include "libbfd.h"
 #include "elf-bfd.h"
 #include "dwarf2.h"
+#include "hashtab.h"
 
 /* The data in the .debug_line statement prologue looks like this.  */
 
@@ -4552,6 +4553,25 @@ stash_comp_unit (struct dwarf2_debug *stash)
   return NULL;
 }
 
+/* Hash function for an asymbol.  */
+
+static hashval_t
+hash_asymbol (const void *sym)
+{
+  const asymbol *asym = sym;
+  return htab_hash_string (asym->name);
+}
+
+/* Equality function for asymbols.  */
+
+static int
+eq_asymbol (const void *a, const void *b)
+{
+  const asymbol *sa = a;
+  const asymbol *sb = b;
+  return strcmp (sa->name, sb->name) == 0;
+}
+
 /* Scan the debug information in PINFO looking for a DW_TAG_subprogram
    abbrev with a DW_AT_low_pc attached to it.  Then lookup that same
    symbol in SYMBOLS and return the difference between the low_pc and
@@ -4562,12 +4582,28 @@ _bfd_dwarf2_find_symbol_bias (asymbol ** symbols, void ** pinfo)
 {
   struct dwarf2_debug *stash;
   struct comp_unit * unit;
+  htab_t sym_hash;
+  bfd_signed_vma result = 0;
+  asymbol ** psym;
 
   stash = (struct dwarf2_debug *) *pinfo;
 
   if (stash == NULL || symbols == NULL)
     return 0;
 
+  sym_hash = htab_create_alloc (10, hash_asymbol, eq_asymbol,
+				NULL, xcalloc, free);
+  for (psym = symbols; * psym != NULL; psym++)
+    {
+      asymbol * sym = * psym;
+
+      if (sym->flags & BSF_FUNCTION && sym->section != NULL)
+	{
+	  void **slot = htab_find_slot (sym_hash, sym, INSERT);
+	  *slot = sym;
+	}
+    }
+
   for (unit = stash->all_comp_units; unit; unit = unit->next_unit)
     {
       struct funcinfo * func;
@@ -4577,24 +4613,24 @@ _bfd_dwarf2_find_symbol_bias (asymbol ** symbols, void ** pinfo)
       for (func = unit->function_table; func != NULL; func = func->prev_func)
 	if (func->name && func->arange.low)
 	  {
-	    asymbol ** psym;
+	    asymbol search, *sym;
 
 	    /* FIXME: Do we need to scan the aranges looking for the lowest pc value ?  */
 
-	    for (psym = symbols; * psym != NULL; psym++)
+	    search.name = func->name;
+	    sym = htab_find (sym_hash, &search);
+	    if (sym != NULL)
 	      {
-		asymbol * sym = * psym;
-
-		if (sym->flags & BSF_FUNCTION
-		    && sym->section != NULL
-		    && strcmp (sym->name, func->name) == 0)
-		  return ((bfd_signed_vma) func->arange.low) -
-		    ((bfd_signed_vma) (sym->value + sym->section->vma));
+		result = ((bfd_signed_vma) func->arange.low) -
+		  ((bfd_signed_vma) (sym->value + sym->section->vma));
+		goto done;
 	      }
 	  }
     }
 
-  return 0;
+ done:
+  htab_delete (sym_hash);
+  return result;
 }
 
 /* Find the source code location of SYMBOL.  If SYMBOL is NULL