Re: [patch] Speed up find_pc_section

Paul Pluzhnikov
2009-07-17T14:55:59Z

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

On Thu, Jul 16, 2009 at 5:24 PM, Paul Pluzhnikov<ppluzhnikov@google.com> wrote:

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

A cleaner patch, with ChangeLog this time.

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 function.
(find_pc_section): Use bsearch.

[-- Attachment #2: gdb-find_pc_section-20090717.txt --]
[-- Type: text/plain, Size: 4368 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 14:52:47 -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.
@@ -394,6 +400,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,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;
}