Speedup dwfl_module_addrsym

[Mark Wielaard <mjw at redhat dot com>]

Hi,

dwfl_module_addrsym is a bit slow because it wants to return global
symbols in preference to local symbols, but first looks at all the local
symbols. To speed this up I wrote the following patches, which
introduces dwfl_module_symtab_global to get the first index of the
global symbols in the symtab. And the uses this in dwfl_module_addrsym
to search through the global symbols first, and only if no symbol was
found, go through the local symbols afterwards.

This gives a nice speedup on readelf -w libstdc++.so.debug for example,
from 35 seconds to 25 seconds, on my machine. The output is exactly the
same.

Comments?

Thanks,

Mark

From 8c8a3c447db2bd2577d184bafdcfe1a21d313584 Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mjw@redhat.com>
Date: Mon, 31 Oct 2011 15:59:23 +0100
Subject: [PATCH 1/2] Add new dwfl_module_symtab_global function.

Return the index of the first global symbol in the module's symbol table,
or -1 when unknown.  All symbols with local binding come first in the
symbol table with local binding.
---
 libdw/ChangeLog                |    4 ++++
 libdw/libdw.map                |    5 +++++
 libdwfl/ChangeLog              |   10 ++++++++++
 libdwfl/dwfl_module_getdwarf.c |   28 ++++++++++++++++++++++++----
 libdwfl/libdwfl.h              |    5 +++++
 libdwfl/libdwflP.h             |    2 ++
 6 files changed, 50 insertions(+), 4 deletions(-)

diff --git a/libdw/ChangeLog b/libdw/ChangeLog
index 1a09b33..1f99c67 100644
--- a/libdw/ChangeLog
+++ b/libdw/ChangeLog
@@ -1,3 +1,7 @@
+2011-10-31  Mark Wielaard  <mjw@redhat.com>
+
+	* libdw.map (ELFUTILS_0.153): New set.  Add dwfl_module_symtab_global.
+
 2011-07-14  Mark Wielaard  <mjw@redhat.com>
 
 	* libdw.h (dwarf_offdie): Fix documentation to mention .debug_info.
diff --git a/libdw/libdw.map b/libdw/libdw.map
index 1f71d03..e598f2d 100644
--- a/libdw/libdw.map
+++ b/libdw/libdw.map
@@ -254,3 +254,8 @@ ELFUTILS_0.149 {
 
     dwfl_dwarf_line;
 } ELFUTILS_0.148;
+
+ELFUTILS_0.153 {
+  global:
+    dwfl_module_symtab_global;
+} ELFUTILS_0.149;
diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index 97caf0b..850d1da 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,5 +1,15 @@
 2011-11-31  Mark Wielaard  <mjw@redhat.com>
 
+	* dwfl_module_getdwarf.c (load_symtab): Take symglobals int arg
+	and fill it in.
+	(find_symtab): Initialize mod->symglobals and pass it to load_symtab.
+	(dwfl_module_symtab_global): New function.
+	* libdwfl/libdwfl.h (dwfl_module_symtab_global): Define and document.
+	* libdwfl/libdwflP.h (Dwfl_Module): Add symglobals field.
+	(dwfl_module_symtab_global): INTDECL.
+
+2011-11-31  Mark Wielaard  <mjw@redhat.com>
+
 	* dwfl_module_addrsym.c (dwfl_module_addrsym): Only update
 	sizeless_sym if needed and closer to desired addr.
 
diff --git a/libdwfl/dwfl_module_getdwarf.c b/libdwfl/dwfl_module_getdwarf.c
index 9c67713..ea60e36 100644
--- a/libdwfl/dwfl_module_getdwarf.c
+++ b/libdwfl/dwfl_module_getdwarf.c
@@ -568,7 +568,7 @@ find_debuginfo (Dwfl_Module *mod)
 static Dwfl_Error
 load_symtab (struct dwfl_file *file, struct dwfl_file **symfile,
 	     Elf_Scn **symscn, Elf_Scn **xndxscn,
-	     size_t *syments, GElf_Word *strshndx)
+	     size_t *syments, int *symglobals, GElf_Word *strshndx)
 {
   bool symtab = false;
   Elf_Scn *scn = NULL;
@@ -584,6 +584,7 @@ load_symtab (struct dwfl_file *file, struct dwfl_file **symfile,
 	    *symfile = file;
 	    *strshndx = shdr->sh_link;
 	    *syments = shdr->sh_size / shdr->sh_entsize;
+	    *symglobals = shdr->sh_info;
 	    if (*xndxscn != NULL)
 	      return DWFL_E_NOERROR;
 	    break;
@@ -844,11 +845,14 @@ find_symtab (Dwfl_Module *mod)
   if (mod->symerr != DWFL_E_NOERROR)
     return;
 
+  mod->symglobals = -1; /* Unknown, unless explicitly set by load_symtab.  */
+
   /* First see if the main ELF file has the debugging information.  */
   Elf_Scn *symscn = NULL, *xndxscn = NULL;
   GElf_Word strshndx;
   mod->symerr = load_symtab (&mod->main, &mod->symfile, &symscn,
-			     &xndxscn, &mod->syments, &strshndx);
+			     &xndxscn, &mod->syments, &mod->symglobals,
+			     &strshndx);
   switch (mod->symerr)
     {
     default:
@@ -867,7 +871,8 @@ find_symtab (Dwfl_Module *mod)
 
 	case DWFL_E_NOERROR:
 	  mod->symerr = load_symtab (&mod->debug, &mod->symfile, &symscn,
-				     &xndxscn, &mod->syments, &strshndx);
+				     &xndxscn, &mod->syments,
+				     &mod->symglobals, &strshndx);
 	  break;
 
 	case DWFL_E_CB:		/* The find_debuginfo hook failed.  */
@@ -906,7 +911,7 @@ find_symtab (Dwfl_Module *mod)
       return;
     }
 
-  /* Cache the data; MOD->syments was set above.  */
+  /* Cache the data; MOD->syments and MOD->symglobals were set above.  */
 
   mod->symstrdata = elf_getdata (elf_getscn (mod->symfile->elf, strshndx),
 				 NULL);
@@ -1086,3 +1091,18 @@ dwfl_module_getsymtab (Dwfl_Module *mod)
   return -1;
 }
 INTDEF (dwfl_module_getsymtab)
+
+int
+dwfl_module_symtab_global (Dwfl_Module *mod)
+{
+  if (mod == NULL)
+    return -1;
+
+  find_symtab (mod);
+  if (mod->symerr == DWFL_E_NOERROR)
+    return mod->symglobals;
+
+  __libdwfl_seterrno (mod->symerr);
+  return -1;
+}
+INTDEF (dwfl_module_symtab_global)
diff --git a/libdwfl/libdwfl.h b/libdwfl/libdwfl.h
index 4ea2796..b2e9eff 100644
--- a/libdwfl/libdwfl.h
+++ b/libdwfl/libdwfl.h
@@ -430,6 +430,11 @@ extern Elf *dwfl_module_getelf (Dwfl_Module *, GElf_Addr *bias);
    or -1 for errors.  */
 extern int dwfl_module_getsymtab (Dwfl_Module *mod);
 
+/* Return the index of the first global symbol in the module's symbol table,
+   or -1 when unknown.  All symbols with local binding come first in the
+   symbol table with local binding.  */
+extern int dwfl_module_symtab_global (Dwfl_Module *mod);
+
 /* Fetch one entry from the module's symbol table.  On errors, returns
    NULL.  If successful, fills in *SYM and returns the string for st_name.
    This works like gelf_getsym except that st_value is always adjusted to
diff --git a/libdwfl/libdwflP.h b/libdwfl/libdwflP.h
index 1f7532b..72dfb26 100644
--- a/libdwfl/libdwflP.h
+++ b/libdwfl/libdwflP.h
@@ -172,6 +172,7 @@ struct Dwfl_Module
   struct dwfl_file *symfile;	/* Either main or debug.  */
   Elf_Data *symdata;		/* Data in the ELF symbol table section.  */
   size_t syments;		/* sh_size / sh_entsize of that section.  */
+  int symglobals;		/* Index of first global symbol of table.  */
   Elf_Data *symstrdata;		/* Data for its string table.  */
   Elf_Data *symxndxdata;	/* Data in the extended section index table. */
 
@@ -498,6 +499,7 @@ INTDECL (dwfl_offline_section_address)
 INTDECL (dwfl_module_relocate_address)
 INTDECL (dwfl_module_dwarf_cfi)
 INTDECL (dwfl_module_eh_cfi)
+INTDECL (dwfl_module_symtab_global)
 
 /* Leading arguments standard to callbacks passed a Dwfl_Module.  */
 #define MODCB_ARGS(mod)	(mod), &(mod)->userdata, (mod)->name, (mod)->low_addr
-- 
1.7.4.4

From b1522084d3c09b6624b861ee75fb4e246a30febb Mon Sep 17 00:00:00 2001
From: Mark Wielaard <mjw@redhat.com>
Date: Mon, 31 Oct 2011 16:18:31 +0100
Subject: [PATCH 2/2] Use dwfl_module_symtab_global in dwfl_module_addrsym to
 speedup search.

---
 libdwfl/ChangeLog             |    6 ++++++
 libdwfl/dwfl_module_addrsym.c |   19 ++++++++++++++++++-
 2 files changed, 24 insertions(+), 1 deletions(-)

diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index 850d1da..1f51bfd 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,5 +1,11 @@
 2011-11-31  Mark Wielaard  <mjw@redhat.com>
 
+	* dwfl_module_addrsym.c (dwfl_module_addrsym): First search all
+	global symbols. Then only when that doesn't provide a match search
+	all local symbols too.
+
+2011-11-31  Mark Wielaard  <mjw@redhat.com>
+
 	* dwfl_module_getdwarf.c (load_symtab): Take symglobals int arg
 	and fill it in.
 	(find_symtab): Initialize mod->symglobals and pass it to load_symtab.
diff --git a/libdwfl/dwfl_module_addrsym.c b/libdwfl/dwfl_module_addrsym.c
index 41ff465..84fdb8b 100644
--- a/libdwfl/dwfl_module_addrsym.c
+++ b/libdwfl/dwfl_module_addrsym.c
@@ -60,6 +60,8 @@ dwfl_module_addrsym (Dwfl_Module *mod, GElf_Addr addr,
   if (syments < 0)
     return NULL;
 
+  int symglobals = INTUSE(dwfl_module_symtab_global) (mod);
+
   /* Return true iff we consider ADDR to lie in the same section as SYM.  */
   GElf_Word addr_shndx = SHN_UNDEF;
   inline bool same_section (const GElf_Sym *sym, GElf_Word shndx)
@@ -104,8 +106,13 @@ dwfl_module_addrsym (Dwfl_Module *mod, GElf_Addr addr,
   /* Keep track of the lowest address a relevant sizeless symbol could have.  */
   GElf_Addr min_label = 0;
 
+  /* First go through global symbols. */
+  int start = symglobals < 0 ? 1 : symglobals;
+  int end = syments;
+
   /* Look through the symbol table for a matching symbol.  */
-  for (int i = 1; i < syments; ++i)
+  search_table:
+  for (int i = start; i < end; ++i)
     {
       GElf_Sym sym;
       GElf_Word shndx;
@@ -168,6 +175,16 @@ dwfl_module_addrsym (Dwfl_Module *mod, GElf_Addr addr,
 	}
     }
 
+  /* If we found nothing searching the global symbols, then try the locals.
+     Unless we have a global sizeless symbol that matches exactly.  */
+  if (closest_name == NULL && start != 1 && symglobals > 1
+      && (sizeless_name == NULL || sizeless_sym.st_value != addr))
+    {
+      start = 1;
+      end = symglobals;
+      goto search_table;
+    }
+
   /* If we found no proper sized symbol to use, fall back to the best
      candidate sizeless symbol we found, if any.  */
   if (closest_name == NULL
-- 
1.7.4.4