Slow readelf for huge ARM binary

[Dmitry Antipov <dantipov at nvidia dot com>]

I have a huge ARM v5 EABI binary with > 6.5M entries in .symtab and > 1.4M entries
in .ARM.exidx tables. With such a binary, 'readelf -u' wastes an (almost) infinite
amount of time doing linear search in find_symbol_for_address. IMHO this should be
fixed with some more advanced stuff, probably the ordered subset of .symtab with
STT_FUNC objects; an attached patch illustrates this idea (ARM-only).

Dmitry

diff --git a/binutils/readelf.c b/binutils/readelf.c
index 00bcb1d..0c8e69e 100644
--- a/binutils/readelf.c
+++ b/binutils/readelf.c
@@ -6484,20 +6484,22 @@ find_symbol_for_address (Elf_Internal_Sym * symtab,
 			 bfd_vma * offset)
 {
   bfd_vma dist = 0x100000;
-  Elf_Internal_Sym * sym;
-  Elf_Internal_Sym * best = NULL;
-  unsigned long i;
+  Elf_Internal_Sym * sym, * beg, * end, * best = NULL;
 
   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)
@@ -6507,6 +6509,10 @@ find_symbol_for_address (Elf_Internal_Sym * symtab,
 	  if (!dist)
 	    break;
 	}
+      if (addr.offset < value)
+	end = sym;
+      else
+	beg = sym + 1;
     }
 
   if (best)
@@ -7234,6 +7240,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 objects.  */
+  unsigned long       nfuns;		/* Number of these objects.  */
   char *              strtab;		/* The file's string table.  */
   unsigned long       strtab_size;	/* Size of string table.  */
 };
@@ -7248,7 +7256,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);
 
@@ -8066,16 +8074,31 @@ decode_arm_unwind (struct arm_unw_aux_info *  aux,
   /* Decode the descriptors.  Not implemented.  */
 }
 
+static int
+symcmp (const void *p, const void *q)
+{
+  Elf_Internal_Sym *sp = (Elf_Internal_Sym *) p, *sq = (Elf_Internal_Sym *) q;
+  return sp->st_value > sq->st_value ? 1 : (sp->st_value < sq->st_value ? -1 : 0);
+}
+
 static void
 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;
@@ -8089,6 +8112,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;
@@ -8152,6 +8176,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);
 }