[patch] Speed up find_pc_section

[Paul Pluzhnikov <ppluzhnikov@google.com>]

[-- Attachment #1: Type: text/plain, Size: 988 bytes --]

Greetings,

While working on something else, I noticed find_pc_section consuming 90%+
of CPU in my GDB profiles :-(

It is called from quite a number of places, and is surprisingly
inefficient. Further, it exhibits yet another quadratic slowdown on number
of objfiles, as the attached test case demonstrates.

Running "perl gen.pl NNN" generates NNN shared libs, and a main executable,
which crashes with NNN+C levels in stack trace, crossing all shared libs.

I then collected timing like this:
time gdb64-cvs -ex run -ex where -ex quit ./a.out > /dev/null

Here are user-time results before the patch (clearly showing non-linear
slowdown):

32:  0m0.426s
64:  0m1.344s
128: 0m5.254s
256: 0m35.792s
512: 4m55.999s

Attached patch turns linear search into binary search, speeding up
find_pc_section drastically :-)

Here are the same user-time results after the patch:

128: 0m1.064s
256: 0m3.062s
512: 0m10.675s

Tested on Linux/x86_64 with no regressions.

Comments?
--
Paul Pluzhnikov

[-- Attachment #2: gdb-find_pc_section-20090716.txt --]
[-- Type: text/plain, Size: 4570 bytes --]

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 00:21:13 -0000
@@ -64,6 +64,18 @@ struct objfile *current_objfile;	/* For 
 struct objfile *symfile_objfile;	/* Main symbol table loaded from */
 struct objfile *rt_common_objfile;	/* For runtime common symbols */
 
+struct address_to_obj_section
+{
+  CORE_ADDR addr;
+  CORE_ADDR endaddr;
+  struct obj_section *section;
+};
+
+/* 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 +106,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.
@@ -394,6 +407,7 @@ unlink_objfile (struct objfile *objfile)
 void
 free_objfile (struct objfile *objfile)
 {
+  objfiles_updated_p += 1;  /* Rebuild section map next time we need it.  */
   if (objfile->separate_debug_objfile)
     {
       free_objfile (objfile->separate_debug_objfile);
@@ -757,22 +771,121 @@ have_minimal_symbols (void)
   return 0;
 }
 
+/* Qsort comparison function.  */
+static int
+section_map_compare (const void *a, const void *b)
+{
+  const struct address_to_obj_section *aa =
+      (const struct address_to_obj_section *) a;
+  const struct address_to_obj_section *bb =
+      (const struct address_to_obj_section *) b;
+
+  if (aa->addr < bb->addr)
+    {
+      gdb_assert (aa->endaddr <= bb->addr);
+      return -1;
+    }
+  else if (aa->addr > bb->addr)
+    {
+      gdb_assert (aa->addr >= bb->endaddr);
+      return 1;
+    }
+  /* This can happen for separate debug-info files.  */
+  gdb_assert (aa->endaddr == bb->endaddr);
+
+  return 0;
+}
+
+/* Update PMAP, PMAP_SIZE with non-TLS sections from all objfiles.  */
+
+static void
+update_section_map (struct address_to_obj_section **pmap,
+                    int *pmap_size)
+{
+  int map_size, idx;
+  struct obj_section *s;
+  struct objfile *objfile;
+  struct address_to_obj_section *map;
+
+  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].section = s;
+        map[idx].addr = obj_section_addr (s);
+        map[idx].endaddr = obj_section_endaddr (s);
+        idx += 1;
+      }
+
+#undef insert_p
+
+  qsort (map, map_size, sizeof (*map), section_map_compare);
+
+  *pmap = map;
+  *pmap_size = map_size;
+}
+
+/* Bsearch comparison function. */
+
+int
+find_pc_section_cmp (const void *key, const void *elt)
+{
+  CORE_ADDR pc = *(CORE_ADDR *) key;
+  const struct address_to_obj_section *entry =
+      (const struct address_to_obj_section *) elt;
+
+  if (pc < entry->addr)
+    return -1;
+  if (pc < entry->endaddr)
+    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)
 {
+  static struct address_to_obj_section *sections;
+  static int num_sections;
+
   struct obj_section *s;
-  struct objfile *objfile;
+  struct address_to_obj_section *aos;
 
   /* 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;
+    }
+
+  aos = bsearch (&pc, sections, num_sections, sizeof (*sections),
+                 find_pc_section_cmp);
+  if (aos)
+    return aos->section;
 
   return NULL;
 }

[-- Attachment #3: gen.pl --]
[-- Type: application/x-perl, Size: 633 bytes --]