Re: gdb script performance

Jean-Marc Saffroy
2006-11-29T02:47:39Z

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2810 bytes --]

Hello,

I'm resurrecting this old thread on gdb performance since I took some time
to look into the problem recently.

On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:

> On Thu, Oct 05, 2006 at 05:29:30PM +0200, Jean-Marc Saffroy wrote:
>> On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:
>>
>> Please find attached gprof output (this is with gdb 6.5 +
>> gdb-lookup-internal-first-3.patch running the lsmaps script I posted
>> earlier).
>>
>> Thanks for helping!
>
> 26.14 381.31 381.31 141867 2.69 3.50 find_pc_sect_psymtab
> 18.54 651.82 270.51 331876 0.82 0.82 find_pc_sect_section
> 17.88 912.69 260.87 144847060 0.00 0.00 lookup_partial_symbol
> 11.01 1073.33 160.64 1254595136 0.00 0.00 strcmp_iw
> 4.98 1145.97 72.64 34010 2.14 16.50 lookup_symbol_aux_psymtabs
> 4.78 1215.73 69.75 9584 7.28 8.12 fixup_section
> 4.46 1280.79 65.06 lbasename
> 3.42 1330.64 49.85 12183 4.09 4.09 lookup_partial_symtab
> 1.83 1357.34 26.70 33844664 0.00 0.00 strcmp_iw_ordered
> 1.68 1381.82 24.48 1288426966 0.00 0.00 symbol_natural_name
> 1.09 1397.71 15.89 1288426966 0.00 0.00 symbol_search_name
>
> Well then. Observations:
> - We're looking up partial symbols way too often.
> - It's taking way too long.
> - And oh my lord is that a lot of calls to the (fairly inefficient)
> strcmp_iw.
>
> It looks like only about three calls to find_pc_sect_psymtab per
> expression evaluation, which is bad but not too bad - sounds like
> a last-searched-item cache may be useful.

Some interesting facts:
- readelf reports no less than 7871 section headers in the vmlinux I'm
analyzing (this is 2.6.18): any attempt to traverse the list of sections
costs a *lot*
- even with the patch lookup-internal-first-3, it seems lookup_symbol_aux
is sometimes called for gdb script vars

Anyway, I followed your advice and added caching to find_pc_sect_symtab
and lookup_symbol_aux, which together divided execution time by 6 on my
benchmark. :-) See gprof output here (baseline is gdb 6.5 with
gdb-lookup-internal-first-3.patch):
http://siegfried.dnsalias.net/~saffroy/gdb-baseline.html
http://siegfried.dnsalias.net/~saffroy/gdb-symcache.html
http://siegfried.dnsalias.net/~saffroy/gdb-symcache-pc_cache.html
Obviously there is still room for improvement with lbasename.

For completeness I have to mention that gprof reports a completely wrong
count of seconds on my system (x86-64 box), but it seems there is only a
bad multiplier somewhere.

Incomplete patches are attached: they lack proper cache invalidation (eg.
on loading of a new object), but let's discuss the approach first.

Cheers,

--
saffroy@gmail.com

[-- Attachment #2: Type: TEXT/PLAIN, Size: 1306 bytes --]

Index: gdb-6.5-prof/gdb/symtab.c
===================================================================
--- gdb-6.5-prof.orig/gdb/symtab.c 2006-11-29 03:27:18.000000000 +0100
+++ gdb-6.5-prof/gdb/symtab.c 2006-11-29 03:27:20.000000000 +0100
@@ -2022,8 +2022,8 @@
/* Find the symtab associated with PC and SECTION. Look through the
psymtabs and read in another symtab if necessary. */

-struct symtab *
-find_pc_sect_symtab (CORE_ADDR pc, asection *section)
+static struct symtab *
+find_pc_sect_symtab_uncached (CORE_ADDR pc, asection *section)
{
struct block *b;
struct blockvector *bv;
@@ -2123,6 +2123,24 @@
return (s);
}

+struct symtab *
+find_pc_sect_symtab (CORE_ADDR pc, asection *section)
+{
+ static CORE_ADDR cached_pc;
+ static asection *cached_section;
+ static struct symtab *cached_symtab;
+ static int try_cache = 0;
+
+ if (try_cache && (cached_pc == pc) && (cached_section == section))
+ return cached_symtab;
+
+ try_cache = 1;
+ cached_pc = pc;
+ cached_section = section;
+ cached_symtab = find_pc_sect_symtab_uncached (pc, section);
+ return cached_symtab;
+}
+
/* Find the symtab associated with PC. Look through the psymtabs and
read in another symtab if necessary. Backward compatibility, no section */

[-- Attachment #3: Type: TEXT/PLAIN, Size: 6375 bytes --]

Index: gdb-6.5-prof/gdb/symtab.c
===================================================================
--- gdb-6.5-prof.orig/gdb/symtab.c 2006-11-27 03:01:22.000000000 +0100
+++ gdb-6.5-prof/gdb/symtab.c 2006-11-28 01:21:28.000000000 +0100
@@ -94,6 +94,20 @@
struct symtab **symtab);

static
+int symcache_lookup (const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symbol **sym,
+ struct symtab **symtab);
+
+static
+void symcache_add (struct symbol *sym,
+ const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symtab **symtab);
+
+static
struct symbol *lookup_symbol_aux_symtabs (int block_index,
const char *name,
const char *linkage_name,
@@ -1113,6 +1127,9 @@
}
}

+ if (symcache_lookup (name, linkage_name, domain, &sym, symtab))
+ return sym;
+
/* Now do whatever is appropriate for the current language to look
up static and global variables. */

@@ -1120,7 +1137,7 @@
block, domain,
symtab);
if (sym != NULL)
- return sym;
+ goto out;

/* Now search all static file-level symbols. Not strictly correct,
but more useful than an error. Do the symtabs first, then check
@@ -1131,16 +1148,19 @@
sym = lookup_symbol_aux_symtabs (STATIC_BLOCK, name, linkage_name,
domain, symtab);
if (sym != NULL)
- return sym;
-
+ goto out;
+
sym = lookup_symbol_aux_psymtabs (STATIC_BLOCK, name, linkage_name,
domain, symtab);
if (sym != NULL)
- return sym;
+ goto out;

if (symtab != NULL)
*symtab = NULL;
- return NULL;
+
+ out:
+ symcache_add (sym, name, linkage_name, domain, symtab);
+ return sym;
}

/* Check to see if the symbol is defined in BLOCK or its superiors.
@@ -1215,6 +1235,177 @@
return NULL;
}

+/* Check for a cached symbol lookup.
+ */
+
+struct symcache_entry {
+ const char *name;
+ const char *linkage_name;
+ domain_enum domain;
+ struct symbol *sym;
+ struct symtab *symtab;
+ struct symcache_entry *next, *prev; /* mru list */
+};
+
+/* max number of entries in symcache */
+#define SYMCACHE_SIZE 256
+
+/* fixed-size hash table of symcache entries */
+static htab_t symcache_hashtab;
+
+/* most recently accessed symcache entry */
+static struct symcache_entry *symcache_newest;
+
+static hashval_t
+symcache_hash(const void *e)
+{
+ struct symcache_entry *entry = (struct symcache_entry *)e;
+
+ return htab_hash_string (entry->name) + entry->domain;
+}
+
+static int
+symcache_eq(const void *e, const void *f)
+{
+ struct symcache_entry *a = (struct symcache_entry *)e;
+ struct symcache_entry *b = (struct symcache_entry *)f;
+
+ return ! strcmp (a->name, b->name)
+ // FIXME && !strcmp(a->linkage_name, b->linkage_name)
+ && (a->domain == b->domain);
+}
+
+static void
+symcache_list_add(struct symcache_entry *entry)
+{
+ if (symcache_newest == NULL)
+ {
+ /* init mru */
+ entry->prev = entry;
+ entry->next = entry;
+ symcache_newest = entry;
+ }
+ else
+ {
+ /* add entry at head of mru */
+ entry->next = symcache_newest;
+ entry->prev = symcache_newest->prev;
+ entry->prev->next = entry;
+ entry->next->prev = entry;
+ symcache_newest = entry;
+ }
+}
+
+static void
+symcache_list_del(struct symcache_entry *entry)
+{
+ /* remove entry from mru */
+ entry->prev->next = entry->next;
+ entry->next->prev = entry->prev;
+}
+
+static void
+symcache_del(void *e)
+{
+ struct symcache_entry *entry = (struct symcache_entry *)e;
+
+ symcache_list_del (entry);
+ free (entry->name);
+ free (entry->linkage_name);
+ free (entry);
+}
+
+static void
+symcache_add (struct symbol *sym,
+ const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symtab **symtab)
+{
+ struct symcache_entry request, *entry, **slot;
+
+ /* initialize on first use */
+ if (!symcache_hashtab)
+ symcache_hashtab = htab_create_alloc (SYMCACHE_SIZE,
+ symcache_hash,
+ symcache_eq,
+ symcache_del,
+ xcalloc,
+ free);
+
+ /* sym can be known, but with unknown symtab: add it if possible */
+ request.name = name;
+ request.linkage_name = linkage_name;
+ request.domain = domain;
+ entry = htab_find (symcache_hashtab, &request);
+ if (entry != HTAB_EMPTY_ENTRY)
+ {
+ if (symtab != NULL)
+ entry->symtab = *symtab;
+ return;
+ }
+
+ /* when cache is full, remove oldest element */
+ if (htab_elements (symcache_hashtab) == SYMCACHE_SIZE)
+ {
+ struct symcache_entry *oldest;
+
+ oldest = symcache_newest->prev;
+ htab_remove_elt (symcache_hashtab, oldest);
+ }
+
+ /* this is really a new entry */
+ entry = xcalloc (1, sizeof(*entry));
+ entry->name = strdup (name);
+ entry->linkage_name = linkage_name ? strdup (linkage_name) : NULL;
+ entry->domain = domain;
+ entry->sym = sym;
+ if (symtab != NULL)
+ entry->symtab = *symtab;
+ symcache_list_add (entry);
+
+ slot = htab_find_slot (symcache_hashtab, entry, INSERT);
+ *slot = entry;
+}
+
+static int
+symcache_lookup (const char *name,
+ const char *linkage_name,
+ const domain_enum domain,
+ struct symbol **sym,
+ struct symtab **symtab)
+{
+ struct symcache_entry request, *entry;
+
+ if (!symcache_hashtab)
+ return 0;
+
+ request.name = name;
+ request.linkage_name = linkage_name;
+ request.domain = domain;
+ entry = htab_find (symcache_hashtab, &request);
+ if (entry == HTAB_EMPTY_ENTRY)
+ return 0;
+
+ if (symtab != NULL)
+ {
+ if (entry->symtab == NULL)
+ /* symtab is requested, but cached entry does not have it */
+ return 0;
+ *symtab = entry->symtab;
+ }
+ *sym = entry->sym;
+
+ /* keep mru list sorted */
+ if (entry != symcache_newest)
+ {
+ symcache_list_del (entry);
+ symcache_list_add (entry);
+ }
+
+ return 1;
+}
+
/* Check to see if the symbol is defined in one of the symtabs.
BLOCK_INDEX should be either GLOBAL_BLOCK or STATIC_BLOCK,
depending on whether or not we want to search global symbols or