Use index of first global symbol to speed up dwfl_module_addrsym search.

Cache 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 before the global symbols.  Use this information to speed
up dwfl_module_addrsym search.

4 files changed, 85 insertions, 54 deletions

diff --git a/libdwfl/ChangeLog b/libdwfl/ChangeLog
index 97caf0bc..0cfa462d 100644
--- a/libdwfl/ChangeLog
+++ b/libdwfl/ChangeLog
@@ -1,5 +1,15 @@
 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.
+	* dwfl_module_getdwarf.c (load_symtab): Take first_global int arg
+	and fill it in.
+	(find_symtab): Initialize mod->first_global and pass it to load_symtab.
+	* libdwfl/libdwflP.h (Dwfl_Module): Add first_global field.
+
+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_addrsym.c b/libdwfl/dwfl_module_addrsym.c
index 41ff4654..9ced0cfb 100644
--- a/libdwfl/dwfl_module_addrsym.c
+++ b/libdwfl/dwfl_module_addrsym.c
@@ -1,5 +1,5 @@
 /* Find debugging and symbol information for a module in libdwfl.
-   Copyright (C) 2005-2010 Red Hat, Inc.
+   Copyright (C) 2005-2011 Red Hat, Inc.
    This file is part of Red Hat elfutils.
 
    Red Hat elfutils is free software; you can redistribute it and/or modify
@@ -105,69 +105,84 @@ dwfl_module_addrsym (Dwfl_Module *mod, GElf_Addr addr,
   GElf_Addr min_label = 0;
 
   /* Look through the symbol table for a matching symbol.  */
-  for (int i = 1; i < syments; ++i)
+  inline void search_table (int start, int end)
     {
-      GElf_Sym sym;
-      GElf_Word shndx;
-      const char *name = INTUSE(dwfl_module_getsym) (mod, i, &sym, &shndx);
-      if (name != NULL && name[0] != '\0'
-	  && sym.st_shndx != SHN_UNDEF
-	  && sym.st_value <= addr
-	  && GELF_ST_TYPE (sym.st_info) != STT_SECTION
-	  && GELF_ST_TYPE (sym.st_info) != STT_FILE
-	  && GELF_ST_TYPE (sym.st_info) != STT_TLS)
+      for (int i = start; i < end; ++i)
 	{
-	  /* Even if we don't choose this symbol, its existence excludes
-	     any sizeless symbol (assembly label) that is below its upper
-	     bound.  */
-	  if (sym.st_value + sym.st_size > min_label)
-	    min_label = sym.st_value + sym.st_size;
-
-	  if (sym.st_size == 0 || addr - sym.st_value < sym.st_size)
+	  GElf_Sym sym;
+	  GElf_Word shndx;
+	  const char *name = INTUSE(dwfl_module_getsym) (mod, i, &sym, &shndx);
+	  if (name != NULL && name[0] != '\0'
+	      && sym.st_shndx != SHN_UNDEF
+	      && sym.st_value <= addr
+	      && GELF_ST_TYPE (sym.st_info) != STT_SECTION
+	      && GELF_ST_TYPE (sym.st_info) != STT_FILE
+	      && GELF_ST_TYPE (sym.st_info) != STT_TLS)
 	    {
-	      /* This symbol is a better candidate than the current one
-		 if it's closer to ADDR or is global when it was local.  */
-	      if (closest_name == NULL
-		  || closest_sym->st_value < sym.st_value
-		  || (GELF_ST_BIND (closest_sym->st_info)
-		      < GELF_ST_BIND (sym.st_info)))
+	      /* Even if we don't choose this symbol, its existence excludes
+		 any sizeless symbol (assembly label) that is below its upper
+		 bound.  */
+	      if (sym.st_value + sym.st_size > min_label)
+		min_label = sym.st_value + sym.st_size;
+
+	      if (sym.st_size == 0 || addr - sym.st_value < sym.st_size)
 		{
-		  if (sym.st_size != 0)
+		  /* This symbol is a better candidate than the current one
+		     if it's closer to ADDR or is global when it was local.  */
+		  if (closest_name == NULL
+		      || closest_sym->st_value < sym.st_value
+		      || (GELF_ST_BIND (closest_sym->st_info)
+			  < GELF_ST_BIND (sym.st_info)))
+		    {
+		      if (sym.st_size != 0)
+			{
+			  *closest_sym = sym;
+			  closest_shndx = shndx;
+			  closest_name = name;
+			}
+		      else if (closest_name == NULL
+			       && sym.st_value >= min_label
+			       && same_section (&sym, shndx))
+			{
+			  /* Handwritten assembly symbols sometimes have no
+			     st_size.  If no symbol with proper size includes
+			     the address, we'll use the closest one that is in
+			     the same section as ADDR.  */
+			  sizeless_sym = sym;
+			  sizeless_shndx = shndx;
+			  sizeless_name = name;
+			}
+		    }
+		  /* When the beginning of its range is no closer,
+		     the end of its range might be.  But do not
+		     replace a global symbol with a local!  */
+		  else if (sym.st_size != 0
+			   && closest_sym->st_value == sym.st_value
+			   && closest_sym->st_size > sym.st_size
+			   && (GELF_ST_BIND (closest_sym->st_info)
+			       <= GELF_ST_BIND (sym.st_info)))
 		    {
 		      *closest_sym = sym;
 		      closest_shndx = shndx;
 		      closest_name = name;
 		    }
-		  else if (closest_name == NULL
-			   && sym.st_value >= min_label
-			   && same_section (&sym, shndx))
-		    {
-		      /* Handwritten assembly symbols sometimes have no
-			 st_size.  If no symbol with proper size includes
-			 the address, we'll use the closest one that is in
-			 the same section as ADDR.  */
-		      sizeless_sym = sym;
-		      sizeless_shndx = shndx;
-		      sizeless_name = name;
-		    }
-		}
-	      /* When the beginning of its range is no closer,
-		 the end of its range might be.  But do not
-		 replace a global symbol with a local!  */
-	      else if (sym.st_size != 0
-		       && closest_sym->st_value == sym.st_value
-		       && closest_sym->st_size > sym.st_size
-		       && (GELF_ST_BIND (closest_sym->st_info)
-			   <= GELF_ST_BIND (sym.st_info)))
-		{
-		  *closest_sym = sym;
-		  closest_shndx = shndx;
-		  closest_name = name;
 		}
 	    }
 	}
     }
 
+  /* First go through global symbols.  mod->first_global is setup by
+     dwfl_module_getsymtab to 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, then all globals.  */
+  search_table (mod->first_global < 0 ? 1 : mod->first_global, syments);
+
+  /* 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 && mod->first_global > 1
+      && (sizeless_name == NULL || sizeless_sym.st_value != addr))
+    search_table (1, mod->first_global);
+
   /* 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
diff --git a/libdwfl/dwfl_module_getdwarf.c b/libdwfl/dwfl_module_getdwarf.c
index 9c677131..14fcd550 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 *first_global, 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;
+	    *first_global = 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->first_global = -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->first_global,
+			     &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->first_global, &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->first_global were set above.  */
 
   mod->symstrdata = elf_getdata (elf_getscn (mod->symfile->elf, strshndx),
 				 NULL);
diff --git a/libdwfl/libdwflP.h b/libdwfl/libdwflP.h
index 1f7532bf..bca82d2e 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 first_global;		/* 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. */