From 948f632f5671aa16c239507652d92f23f7713703 Mon Sep 17 00:00:00 2001 From: Dmitry Antipov Date: Tue, 24 Feb 2015 13:21:10 +0000 Subject: [PATCH] Speed up the display of unwind tables by using a binary chop search to locate function symbols. * readelf.c (find_symbol_for_address): Use a binary search to speed up symbol location. Skip check for function symbol type. (*_unw_aux_info): Add funtab and nfuns fields contains a sorted list of function symbols. (dump_ia64_unwind): Initialise the funtab and nfuns fields and pass them to find_symbol_for_address. (dump_hppa_unwind): Likewise. (arm_print_vma_and_name): Pass funtab to find_symbol_for_address. (dump_arm_unwind): Initialise the funtab and nfuns fields. --- binutils/ChangeLog | 12 +++ binutils/readelf.c | 233 +++++++++++++++++++++++++++++++++-------------------- 2 files changed, 159 insertions(+), 86 deletions(-) diff --git a/binutils/ChangeLog b/binutils/ChangeLog index 1128b4a..a462145 100644 --- a/binutils/ChangeLog +++ b/binutils/ChangeLog @@ -1,3 +1,15 @@ +2015-02-24 Dmitry Antipov + + * readelf.c (find_symbol_for_address): Use a binary search to + speed up symbol location. Skip check for function symbol type. + (*_unw_aux_info): Add funtab and nfuns fields contains a sorted + list of function symbols. + (dump_ia64_unwind): Initialise the funtab and nfuns fields and + pass them to find_symbol_for_address. + (dump_hppa_unwind): Likewise. + (arm_print_vma_and_name): Pass funtab to find_symbol_for_address. + (dump_arm_unwind): Initialise the funtab and nfuns fields. + 2015-02-24 Nick Clifton * objdump.c (dump_section): Extend the warning message displayed diff --git a/binutils/readelf.c b/binutils/readelf.c index 66b8f98..7394e76 100644 --- a/binutils/readelf.c +++ b/binutils/readelf.c @@ -567,7 +567,7 @@ printable_section_name (Elf_Internal_Shdr * sec) { if (remaining < 2) break; - + * buf ++ = '^'; * buf ++ = c + 0x40; remaining -= 2; @@ -3139,7 +3139,7 @@ get_machine_flags (unsigned e_flags, unsigned e_machine) if (e_flags & EF_SH_FDPIC) strcat (buf, ", fdpic"); break; - + case EM_OR1K: if (e_flags & EF_OR1K_NODELAY) strcat (buf, ", no delay"); @@ -6439,71 +6439,53 @@ process_relocs (FILE * file) return 1; } -/* Process the unwind section. */ - -#include "unwind-ia64.h" - /* An absolute address consists of a section and an offset. If the section is NULL, the offset itself is the address, otherwise, the address equals to LOAD_ADDRESS(section) + offset. */ struct absaddr - { - unsigned short section; - bfd_vma offset; - }; +{ + unsigned short section; + bfd_vma offset; +}; #define ABSADDR(a) \ ((a).section \ ? section_headers [(a).section].sh_addr + (a).offset \ : (a).offset) -struct ia64_unw_table_entry - { - struct absaddr start; - struct absaddr end; - struct absaddr info; - }; - -struct ia64_unw_aux_info - { - - struct ia64_unw_table_entry *table; /* Unwind table. */ - unsigned long table_len; /* Length of unwind table. */ - unsigned char * info; /* Unwind info. */ - unsigned long info_size; /* Size of unwind info. */ - bfd_vma info_addr; /* starting address of unwind info. */ - bfd_vma seg_base; /* Starting address of segment. */ - Elf_Internal_Sym * symtab; /* The symbol table. */ - unsigned long nsyms; /* Number of symbols. */ - char * strtab; /* The string table. */ - unsigned long strtab_size; /* Size of string table. */ - }; +/* Find the nearest symbol at or below ADDR. Returns the symbol + name, if found, and the offset from the symbol to ADDR. */ static void find_symbol_for_address (Elf_Internal_Sym * symtab, - unsigned long nsyms, - const char * strtab, - unsigned long strtab_size, - struct absaddr addr, - const char ** symname, - bfd_vma * offset) + unsigned long nsyms, + const char * strtab, + unsigned long strtab_size, + struct absaddr addr, + const char ** symname, + bfd_vma * offset) { bfd_vma dist = 0x100000; Elf_Internal_Sym * sym; + Elf_Internal_Sym * beg; + Elf_Internal_Sym * end; Elf_Internal_Sym * best = NULL; - unsigned long i; REMOVE_ARCH_BITS (addr.offset); + beg = symtab; + end = symtab + nsyms; - for (i = 0, sym = symtab; i < nsyms; ++i, ++sym) + while (beg < end) { - bfd_vma value = sym->st_value; + bfd_vma value; + + sym = beg + (end - beg) / 2; + value = sym->st_value; REMOVE_ARCH_BITS (value); - if (ELF_ST_TYPE (sym->st_info) == STT_FUNC - && sym->st_name != 0 + if (sym->st_name != 0 && (addr.section == SHN_UNDEF || addr.section == sym->st_shndx) && addr.offset >= value && addr.offset - value < dist) @@ -6513,6 +6495,11 @@ find_symbol_for_address (Elf_Internal_Sym * symtab, if (!dist) break; } + + if (addr.offset < value) + end = sym; + else + beg = sym + 1; } if (best) @@ -6527,12 +6514,56 @@ find_symbol_for_address (Elf_Internal_Sym * symtab, *offset = addr.offset; } +static int +symcmp (const void *p, const void *q) +{ + Elf_Internal_Sym *sp = (Elf_Internal_Sym *) p; + Elf_Internal_Sym *sq = (Elf_Internal_Sym *) q; + + return sp->st_value > sq->st_value ? 1 : (sp->st_value < sq->st_value ? -1 : 0); +} + +/* Process the unwind section. */ + +#include "unwind-ia64.h" + +struct ia64_unw_table_entry +{ + struct absaddr start; + struct absaddr end; + struct absaddr info; +}; + +struct ia64_unw_aux_info +{ + struct ia64_unw_table_entry *table; /* Unwind table. */ + unsigned long table_len; /* Length of unwind table. */ + unsigned char * info; /* Unwind info. */ + unsigned long info_size; /* Size of unwind info. */ + bfd_vma info_addr; /* Starting address of unwind info. */ + bfd_vma seg_base; /* Starting address of segment. */ + Elf_Internal_Sym * symtab; /* The symbol table. */ + unsigned long nsyms; /* Number of symbols. */ + Elf_Internal_Sym * funtab; /* Sorted table of STT_FUNC symbols. */ + unsigned long nfuns; /* Number of entries in funtab. */ + char * strtab; /* The string table. */ + unsigned long strtab_size; /* Size of string table. */ +}; + static void dump_ia64_unwind (struct ia64_unw_aux_info * aux) { struct ia64_unw_table_entry * tp; + unsigned long j, nfuns; int in_body; + aux->funtab = xmalloc (aux->nsyms * sizeof (Elf_Internal_Sym)); + for (nfuns = 0, j = 0; j < aux->nsyms; j++) + if (aux->symtab[j].st_value && ELF_ST_TYPE (aux->symtab[j].st_info) == STT_FUNC) + aux->funtab[nfuns++] = aux->symtab[j]; + aux->nfuns = nfuns; + qsort (aux->funtab, aux->nfuns, sizeof (Elf_Internal_Sym), symcmp); + for (tp = aux->table; tp < aux->table + aux->table_len; ++tp) { bfd_vma stamp; @@ -6542,7 +6573,7 @@ dump_ia64_unwind (struct ia64_unw_aux_info * aux) const unsigned char * end; const char * procname; - find_symbol_for_address (aux->symtab, aux->nsyms, aux->strtab, + find_symbol_for_address (aux->funtab, aux->nfuns, aux->strtab, aux->strtab_size, tp->start, &procname, &offset); fputs ("\n<", stdout); @@ -6598,6 +6629,8 @@ dump_ia64_unwind (struct ia64_unw_aux_info * aux) for (dp = head + 8; dp < end;) dp = unw_decode (dp, in_body, & in_body); } + + free (aux->funtab); } static bfd_boolean @@ -6698,7 +6731,7 @@ slurp_ia64_unwind_table (FILE * file, warn (_("Skipping unknown relocation type: %u\n"), get_reloc_type (rp->r_info)); continue; } - + if (! const_strneq (relname, "R_IA64_SEGREL")) { warn (_("Skipping unexpected relocation type: %s\n"), relname); @@ -6896,7 +6929,7 @@ struct hppa_unw_table_entry { struct absaddr start; struct absaddr end; - unsigned int Cannot_unwind:1; /* 0 */ + unsigned int Cannot_unwind:1; /* 0 */ unsigned int Millicode:1; /* 1 */ unsigned int Millicode_save_sr0:1; /* 2 */ unsigned int Region_description:2; /* 3..4 */ @@ -6905,52 +6938,62 @@ struct hppa_unw_table_entry unsigned int Entry_FR:4; /* number saved */ /* 7..10 */ unsigned int Entry_GR:5; /* number saved */ /* 11..15 */ unsigned int Args_stored:1; /* 16 */ - unsigned int Variable_Frame:1; /* 17 */ - unsigned int Separate_Package_Body:1; /* 18 */ + unsigned int Variable_Frame:1; /* 17 */ + unsigned int Separate_Package_Body:1; /* 18 */ unsigned int Frame_Extension_Millicode:1; /* 19 */ - unsigned int Stack_Overflow_Check:1; /* 20 */ - unsigned int Two_Instruction_SP_Increment:1; /* 21 */ + unsigned int Stack_Overflow_Check:1; /* 20 */ + unsigned int Two_Instruction_SP_Increment:1;/* 21 */ unsigned int Ada_Region:1; /* 22 */ unsigned int cxx_info:1; /* 23 */ - unsigned int cxx_try_catch:1; /* 24 */ - unsigned int sched_entry_seq:1; /* 25 */ + unsigned int cxx_try_catch:1; /* 24 */ + unsigned int sched_entry_seq:1; /* 25 */ unsigned int reserved2:1; /* 26 */ - unsigned int Save_SP:1; /* 27 */ - unsigned int Save_RP:1; /* 28 */ + unsigned int Save_SP:1; /* 27 */ + unsigned int Save_RP:1; /* 28 */ unsigned int Save_MRP_in_frame:1; /* 29 */ unsigned int extn_ptr_defined:1; /* 30 */ - unsigned int Cleanup_defined:1; /* 31 */ + unsigned int Cleanup_defined:1; /* 31 */ - unsigned int MPE_XL_interrupt_marker:1; /* 0 */ - unsigned int HP_UX_interrupt_marker:1; /* 1 */ + unsigned int MPE_XL_interrupt_marker:1; /* 0 */ + unsigned int HP_UX_interrupt_marker:1; /* 1 */ unsigned int Large_frame:1; /* 2 */ - unsigned int Pseudo_SP_Set:1; /* 3 */ + unsigned int Pseudo_SP_Set:1; /* 3 */ unsigned int reserved4:1; /* 4 */ unsigned int Total_frame_size:27; /* 5..31 */ }; struct hppa_unw_aux_info - { - struct hppa_unw_table_entry *table; /* Unwind table. */ - unsigned long table_len; /* Length of unwind table. */ - bfd_vma seg_base; /* Starting address of segment. */ - Elf_Internal_Sym * symtab; /* The symbol table. */ - unsigned long nsyms; /* Number of symbols. */ - char * strtab; /* The string table. */ - unsigned long strtab_size; /* Size of string table. */ - }; +{ + struct hppa_unw_table_entry * table; /* Unwind table. */ + unsigned long table_len; /* Length of unwind table. */ + bfd_vma seg_base; /* Starting address of segment. */ + Elf_Internal_Sym * symtab; /* The symbol table. */ + unsigned long nsyms; /* Number of symbols. */ + Elf_Internal_Sym * funtab; /* Sorted table of STT_FUNC symbols. */ + unsigned long nfuns; /* Number of entries in funtab. */ + char * strtab; /* The string table. */ + unsigned long strtab_size; /* Size of string table. */ +}; static void dump_hppa_unwind (struct hppa_unw_aux_info * aux) { struct hppa_unw_table_entry * tp; + unsigned long j, nfuns; + + aux->funtab = xmalloc (aux->nsyms * sizeof (Elf_Internal_Sym)); + for (nfuns = 0, j = 0; j < aux->nsyms; j++) + if (aux->symtab[j].st_value && ELF_ST_TYPE (aux->symtab[j].st_info) == STT_FUNC) + aux->funtab[nfuns++] = aux->symtab[j]; + aux->nfuns = nfuns; + qsort (aux->funtab, aux->nfuns, sizeof (Elf_Internal_Sym), symcmp); for (tp = aux->table; tp < aux->table + aux->table_len; ++tp) { bfd_vma offset; const char * procname; - find_symbol_for_address (aux->symtab, aux->nsyms, aux->strtab, + find_symbol_for_address (aux->funtab, aux->nfuns, aux->strtab, aux->strtab_size, tp->start, &procname, &offset); @@ -7004,6 +7047,8 @@ dump_hppa_unwind (struct hppa_unw_aux_info * aux) } printf ("\n"); + + free (aux->funtab); } static int @@ -7240,6 +7285,8 @@ struct arm_unw_aux_info FILE * file; /* The file containing the unwind sections. */ Elf_Internal_Sym * symtab; /* The file's symbol table. */ unsigned long nsyms; /* Number of symbols. */ + Elf_Internal_Sym * funtab; /* Sorted table of STT_FUNC symbols. */ + unsigned long nfuns; /* Number of these symbols. */ char * strtab; /* The file's string table. */ unsigned long strtab_size; /* Size of string table. */ }; @@ -7254,7 +7301,7 @@ arm_print_vma_and_name (struct arm_unw_aux_info *aux, if (addr.section == SHN_UNDEF) addr.offset = fn; - find_symbol_for_address (aux->symtab, aux->nsyms, aux->strtab, + find_symbol_for_address (aux->funtab, aux->nfuns, aux->strtab, aux->strtab_size, addr, &procname, &sym_offset); @@ -7549,11 +7596,13 @@ decode_tic6x_unwind_regmask (unsigned int mask) printf ("0x%02x ", OP) static void -decode_arm_unwind_bytecode (struct arm_unw_aux_info *aux, - unsigned int word, unsigned int remaining, - unsigned int more_words, - bfd_vma data_offset, Elf_Internal_Shdr *data_sec, - struct arm_section *data_arm_sec) +decode_arm_unwind_bytecode (struct arm_unw_aux_info * aux, + unsigned int word, + unsigned int remaining, + unsigned int more_words, + bfd_vma data_offset, + Elf_Internal_Shdr * data_sec, + struct arm_section * data_arm_sec) { struct absaddr addr; @@ -7760,11 +7809,13 @@ decode_arm_unwind_bytecode (struct arm_unw_aux_info *aux, } static void -decode_tic6x_unwind_bytecode (struct arm_unw_aux_info *aux, - unsigned int word, unsigned int remaining, - unsigned int more_words, - bfd_vma data_offset, Elf_Internal_Shdr *data_sec, - struct arm_section *data_arm_sec) +decode_tic6x_unwind_bytecode (struct arm_unw_aux_info * aux, + unsigned int word, + unsigned int remaining, + unsigned int more_words, + bfd_vma data_offset, + Elf_Internal_Shdr * data_sec, + struct arm_section * data_arm_sec) { struct absaddr addr; @@ -7882,7 +7933,7 @@ decode_tic6x_unwind_bytecode (struct arm_unw_aux_info *aux, warn (_("Corrupt stack pointer adjustment detected\n")); return; } - + offset = read_uleb128 (buf, &len, buf + i + 1); assert (len == i + 1); offset = offset * 8 + 0x408; @@ -8077,11 +8128,19 @@ dump_arm_unwind (struct arm_unw_aux_info *aux, Elf_Internal_Shdr *exidx_sec) { struct arm_section exidx_arm_sec, extab_arm_sec; unsigned int i, exidx_len; + unsigned long j, nfuns; memset (&exidx_arm_sec, 0, sizeof (exidx_arm_sec)); memset (&extab_arm_sec, 0, sizeof (extab_arm_sec)); exidx_len = exidx_sec->sh_size / 8; + aux->funtab = xmalloc (aux->nsyms * sizeof (Elf_Internal_Sym)); + for (nfuns = 0, j = 0; j < aux->nsyms; j++) + if (aux->symtab[j].st_value && ELF_ST_TYPE (aux->symtab[j].st_info) == STT_FUNC) + aux->funtab[nfuns++] = aux->symtab[j]; + aux->nfuns = nfuns; + qsort (aux->funtab, aux->nfuns, sizeof (Elf_Internal_Sym), symcmp); + for (i = 0; i < exidx_len; i++) { unsigned int exidx_fn, exidx_entry; @@ -8095,6 +8154,7 @@ dump_arm_unwind (struct arm_unw_aux_info *aux, Elf_Internal_Shdr *exidx_sec) || ! get_unwind_section_word (aux, & exidx_arm_sec, exidx_sec, 8 * i + 4, & exidx_entry, & entry_addr, NULL)) { + free (aux->funtab); arm_free_section (& exidx_arm_sec); arm_free_section (& extab_arm_sec); return; @@ -8158,6 +8218,7 @@ dump_arm_unwind (struct arm_unw_aux_info *aux, Elf_Internal_Shdr *exidx_sec) printf ("\n"); + free (aux->funtab); arm_free_section (&exidx_arm_sec); arm_free_section (&extab_arm_sec); } @@ -9751,7 +9812,7 @@ process_version_sections (FILE * file) _("version def")) == NULL) { ivd.vd_next = 0; - /* PR 17531: file: 046-1082287-0.004. */ + /* PR 17531: file: 046-1082287-0.004. */ ivd.vd_ndx = (data[cnt + j] & VERSYM_VERSION) + 1; break; } @@ -10108,7 +10169,7 @@ get_dynamic_data (FILE * file, bfd_size_type number, unsigned int ent_size) (unsigned long long) number, ent_size); return NULL; } - + /* Be kind to memory chekers (eg valgrind, address sanitizer) by not attempting to allocate memory when the read is bound to fail. */ if (ent_size * number > current_file_size) @@ -13849,7 +13910,7 @@ process_mips_specific (FILE * file) /* Find the section header so that we get the size. */ sect = find_section_by_type (SHT_MIPS_OPTIONS); - /* PR 17533 file: 012-277276-0.004. */ + /* PR 17533 file: 012-277276-0.004. */ if (sect == NULL) { error (_("No MIPS_OPTIONS header found\n")); @@ -14159,7 +14220,7 @@ process_mips_specific (FILE * file) error (_("Too many GOT symbols: %lu\n"), (unsigned long) symtabno); return 0; } - + offset = offset_from_vma (file, pltgot, global_end - pltgot); data = (unsigned char *) get_data (NULL, file, offset, global_end - pltgot, 1, @@ -14925,7 +14986,7 @@ print_ia64_vms_note (Elf_Internal_Note * pnote) case NT_VMS_FPMODE: printf (_(" Floating Point mode: ")); printf ("0x%016" BFD_VMA_FMT "x\n", - (bfd_vma)byte_get ((unsigned char *)pnote->descdata, 8)); + (bfd_vma) byte_get ((unsigned char *)pnote->descdata, 8)); break; case NT_VMS_LINKTIME: printf (_(" Link time: ")); @@ -14948,9 +15009,9 @@ print_ia64_vms_note (Elf_Internal_Note * pnote) ((bfd_int64_t) byte_get ((unsigned char *)pnote->descdata + 8, 8)); printf (_("\n Link flags : ")); printf ("0x%016" BFD_VMA_FMT "x\n", - (bfd_vma)byte_get ((unsigned char *)pnote->descdata + 16, 8)); + (bfd_vma) byte_get ((unsigned char *)pnote->descdata + 16, 8)); printf (_(" Header flags: 0x%08x\n"), - (unsigned)byte_get ((unsigned char *)pnote->descdata + 24, 4)); + (unsigned) byte_get ((unsigned char *)pnote->descdata + 24, 4)); printf (_(" Image id : %s\n"), pnote->descdata + 32); break; #endif -- 2.7.4