From 0e70b27ba900581df8e23cbbd4612176f869d796 Mon Sep 17 00:00:00 2001 From: "H.J. Lu" Date: Mon, 5 Mar 2018 03:44:46 -0800 Subject: [PATCH] Use binary search on dynamic relocations Replace linear search with binary search on dynamic relocations. After finding a match, scan backward to the first matching relocation, then scan forward for a matching relocation with non-absolute symbol. On Fedora 27 x86-64, time for "objdump -d" on libxul.so from RHEL 7.4 x86-64 went from 134.46user 0.12system 2:15.03elapsed to 8.49user 0.14system 0:08.64elapsed PR binutils/22911 * objdump.c (is_significant_symbol_name): Return TRUE for all .plt* sections. (find_symbol_for_address): Replace linear search with binary search on dynamic relocations. --- binutils/ChangeLog | 8 ++++++ binutils/objdump.c | 61 +++++++++++++++++++++++++++++++--------------- 2 files changed, 50 insertions(+), 19 deletions(-) diff --git a/binutils/ChangeLog b/binutils/ChangeLog index 067dd95e1e4..8af73448357 100644 --- a/binutils/ChangeLog +++ b/binutils/ChangeLog @@ -1,3 +1,11 @@ +2018-03-05 H.J. Lu + + PR binutils/22911 + * objdump.c (is_significant_symbol_name): Return TRUE for all + .plt* sections. + (find_symbol_for_address): Replace linear search with binary + search on dynamic relocations. + 2018-03-01 Nick Clifton PR 22905 diff --git a/binutils/objdump.c b/binutils/objdump.c index 37a9f0d2e16..f4d05bb22d3 100644 --- a/binutils/objdump.c +++ b/binutils/objdump.c @@ -664,9 +664,7 @@ slurp_dynamic_symtab (bfd *abfd) static bfd_boolean is_significant_symbol_name (const char * name) { - return strcmp (name, ".plt") == 0 - || strcmp (name, ".got") == 0 - || strcmp (name, ".plt.got") == 0; + return strncmp (name, ".plt", 4) == 0 || strcmp (name, ".got") == 0; } /* Filter out (in place) symbols that are useless for disassembly. @@ -937,6 +935,7 @@ find_symbol_for_address (bfd_vma vma, asection *sec; unsigned int opb; bfd_boolean want_section; + long rel_count; if (sorted_symcount < 1) return NULL; @@ -1065,33 +1064,57 @@ find_symbol_for_address (bfd_vma vma, and we have dynamic relocations available, then we can produce a better result by matching a relocation to the address and using the symbol associated with that relocation. */ + rel_count = aux->dynrelcount; if (!want_section - && aux->dynrelbuf != NULL && sorted_syms[thisplace]->value != vma + && rel_count > 0 + && aux->dynrelbuf != NULL + && aux->dynrelbuf[0]->address <= vma + && aux->dynrelbuf[rel_count - 1]->address >= vma /* If we have matched a synthetic symbol, then stick with that. */ && (sorted_syms[thisplace]->flags & BSF_SYNTHETIC) == 0) { - long rel_count; - arelent ** rel_pp; + arelent ** rel_low; + arelent ** rel_high; - for (rel_count = aux->dynrelcount, rel_pp = aux->dynrelbuf; - rel_count--;) + rel_low = aux->dynrelbuf; + rel_high = rel_low + rel_count - 1; + while (rel_low <= rel_high) { - arelent * rel = rel_pp[rel_count]; + arelent **rel_mid = &rel_low[(rel_high - rel_low) / 2]; + arelent * rel = *rel_mid; - if (rel->address == vma - && rel->sym_ptr_ptr != NULL - /* Absolute relocations do not provide a more helpful symbolic address. */ - && ! bfd_is_abs_section ((* rel->sym_ptr_ptr)->section)) + if (rel->address == vma) { - if (place != NULL) - * place = thisplace; - return * rel->sym_ptr_ptr; + /* Absolute relocations do not provide a more helpful + symbolic address. Find a non-absolute relocation + with the same address. */ + arelent **rel_vma = rel_mid; + for (rel_mid--; + rel_mid >= rel_low && rel_mid[0]->address == vma; + rel_mid--) + rel_vma = rel_mid; + + for (; rel_vma <= rel_high && rel_vma[0]->address == vma; + rel_vma++) + { + rel = *rel_vma; + if (rel->sym_ptr_ptr != NULL + && ! bfd_is_abs_section ((* rel->sym_ptr_ptr)->section)) + { + if (place != NULL) + * place = thisplace; + return * rel->sym_ptr_ptr; + } + } + break; } - /* We are scanning backwards, so if we go below the target address - we have failed. */ - if (rel_pp[rel_count]->address < vma) + if (vma < rel->address) + rel_high = rel_mid; + else if (vma >= rel_mid[1]->address) + rel_low = rel_mid + 1; + else break; } } -- 2.30.2