[patch] Speed up find_pc_section

[Paul Pluzhnikov]

On Fri, Jul 17, 2009 at 8:06 AM, Tom Tromey<tromey@redhat.com> wrote:

> Paul> +static int objfiles_updated_p;
>
> This (plus the map itself) seems like another thing that will have to be
> per-inferior or per-address-space.  But, perhaps we aren't quite ready
> for that yet.

Yes, this would definitely need to be modified to be per-address-space.

> Paul> +  objfiles_updated_p += 1;  /* Rebuild section map next time we need it.  */
>
> It seems like we would need one of these in objfile_relocate

Yes, looks like it. Added.

> and maybe in reread_symbols.  What do you think?

Hmm, this one is trickier (I don't want to make objfiles_updated_p global).

I moved the 'objfiles_updated_p += 1' from free_objfile() into
clear_objfile_data() -- that's called from reread_symbols() as well.

> Paul> +int
> Paul> +find_pc_section_cmp (const void *key, const void *elt)
>
> Should be static.

Caught this one in the followup patch :-)

Here is the update.
Re-tested on Linux/x86_64 with no regressions.

Thanks,
-- 
Paul Pluzhnikov

2009-07-17  Paul Pluzhnikov  <ppluzhnikov@google.com>

       * objfiles.c (objfiles_updated_p): New variable.
       (qsort_cmp, bsearch_cmp, update_section_map): New functions.
       (find_pc_section): Use bsearch.
-------------- next part --------------
Index: objfiles.c
===================================================================
RCS file: /cvs/src/src/gdb/objfiles.c,v
retrieving revision 1.85
diff -u -p -u -r1.85 objfiles.c
--- objfiles.c	14 Jul 2009 14:55:06 -0000	1.85
+++ objfiles.c	17 Jul 2009 16:23:30 -0000
@@ -64,6 +64,11 @@ struct objfile *current_objfile;	/* For 
 struct objfile *symfile_objfile;	/* Main symbol table loaded from */
 struct objfile *rt_common_objfile;	/* For runtime common symbols */
 
+/* Records whether any objfiles appeared or disappeared since we last updated
+   address to obj section map.  */
+
+static int objfiles_updated_p;
+
 /* Locate all mappable sections of a BFD file. 
    objfile_p_char is a char * to get it through
    bfd_map_over_sections; we cast it back to its proper type.  */
@@ -94,6 +99,7 @@ add_to_objfile_sections (struct bfd *abf
   obstack_grow (&objfile->objfile_obstack, (char *) &section, sizeof (section));
   objfile->sections_end
     = (struct obj_section *) (((size_t) objfile->sections_end) + 1);
+  objfiles_updated_p += 1;  /* Rebuild section map next time we need it.  */
 }
 
 /* Builds a section table for OBJFILE.
@@ -676,6 +682,7 @@ objfile_relocate (struct objfile *objfil
 
   /* Relocate breakpoints as necessary, after things are relocated. */
   breakpoint_re_set ();
+  objfiles_updated_p += 1;  /* Rebuild section map next time we need it.  */
 }
 

 /* Many places in gdb want to test just to see if we have any partial
@@ -757,23 +764,113 @@ have_minimal_symbols (void)
   return 0;
 }
 
+/* Qsort comparison function.  */
+
+static int
+qsort_cmp (const void *a, const void *b)
+{
+  const struct obj_section *sect1 = *(const struct obj_section **) a;
+  const struct obj_section *sect2 = *(const struct obj_section **) b;
+  const CORE_ADDR sect1_addr = obj_section_addr (sect1);
+  const CORE_ADDR sect2_addr = obj_section_addr (sect2);
+
+  if (sect1_addr < sect2_addr)
+    {
+      gdb_assert (obj_section_endaddr (sect1) <= sect2_addr);
+      return -1;
+    }
+  else if (sect1_addr > sect2_addr)
+    {
+      gdb_assert (sect1_addr >= obj_section_endaddr (sect2));
+      return 1;
+    }
+  /* This can happen for separate debug-info files.  */
+  gdb_assert (obj_section_endaddr (sect1) == obj_section_endaddr (sect2));
+
+  return 0;
+}
+
+/* Update PMAP, PMAP_SIZE with non-TLS sections from all objfiles.  */
+
+static void
+update_section_map (struct obj_section ***pmap, int *pmap_size)
+{
+  int map_size, idx;
+  struct obj_section *s, **map;
+  struct objfile *objfile;
+
+  gdb_assert (objfiles_updated_p != 0);
+
+  map = *pmap;
+  xfree (map);
+
+#define insert_p(objf, sec) \
+  ((bfd_get_section_flags ((objf)->obfd, (sec)->the_bfd_section) \
+    & SEC_THREAD_LOCAL) == 0)
+
+  map_size = 0;
+  ALL_OBJSECTIONS (objfile, s)
+    if (insert_p (objfile, s))
+      map_size += 1;
+
+  map = xmalloc (map_size * sizeof (*map));
+
+  idx = 0;
+  ALL_OBJSECTIONS (objfile, s)
+    if (insert_p (objfile, s))
+      map[idx++] = s;
+
+#undef insert_p
+
+  qsort (map, map_size, sizeof (*map), qsort_cmp);
+
+  *pmap = map;
+  *pmap_size = map_size;
+}
+
+/* Bsearch comparison function. */
+
+static int
+bsearch_cmp (const void *key, const void *elt)
+{
+  const CORE_ADDR pc = *(CORE_ADDR *) key;
+  const struct obj_section *section = *(const struct obj_section **) elt;
+
+  if (pc < obj_section_addr (section))
+    return -1;
+  if (pc < obj_section_endaddr (section))
+    return 0;
+  return 1;
+}
+
 /* Returns a section whose range includes PC or NULL if none found.   */
 
 struct obj_section *
 find_pc_section (CORE_ADDR pc)
 {
-  struct obj_section *s;
-  struct objfile *objfile;
+  static struct obj_section **sections;
+  static int num_sections;
+
+  struct obj_section *s, **sp;
 
   /* Check for mapped overlay section first.  */
   s = find_pc_mapped_section (pc);
   if (s)
     return s;
 
-  ALL_OBJSECTIONS (objfile, s)
-    if (obj_section_addr (s) <= pc && pc < obj_section_endaddr (s))
-      return s;
+  if (objfiles_updated_p != 0)
+    {
+      update_section_map (&sections, &num_sections);
+
+      /* Don't need updates to section map until objfiles are added
+         or removed.  */
+      objfiles_updated_p = 0;
+    }
 
+  sp = (struct obj_section **) bsearch (&pc, sections, num_sections,
+					sizeof (*sections), bsearch_cmp);
+  if (sp != NULL)
+    return *sp;
   return NULL;
 }
 
@@ -876,6 +973,7 @@ clear_objfile_data (struct objfile *objf
       registration->data->cleanup (objfile, objfile->data[i]);
 
   memset (objfile->data, 0, objfile->num_data * sizeof (void *));
+  objfiles_updated_p += 1;  /* Rebuild section map next time we need it.  */
 }
 
 void