aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTom Tromey <tromey@adacore.com>2019-08-15 07:33:20 -0600
committerTom Tromey <tromey@adacore.com>2019-08-19 08:46:21 -0600
commit3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7 (patch)
tree3d8534031d90c39c7fbae258959d25d3caf8288a
parentd292364e95fc9c8230b678d9026f285850074c02 (diff)
downloadgdb-3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7.zip
gdb-3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7.tar.gz
gdb-3eb185c97d8170b3f3a2b5edab4fbbd56f53f6f7.tar.bz2
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.
-rw-r--r--bfd/ChangeLog5
-rw-r--r--bfd/dwarf2.c56
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