[PATCH] gdb script performance

[Jean-Marc Saffroy <saffroy@gmail.com>]

Hi folks,

It seems the patches I posted yesterday on the gdb list have gone 
completely unnoticed, so I guess I should resend them here.

Back in October, I had reported performance problems I observed when 
scripting gdb to analyze a kdump core, and even after applying the patch 
gdb-lookup-internal-first-3, gprof showed something like this:
   http://jeanmarc.saffroy.free.fr/gdb/gdb-baseline.html

Daniel Jacobowitz suggested the following:

On Thu, 5 Oct 2006, Daniel Jacobowitz wrote:

>  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.

Recently I took some time and followed Daniel's advice, ie. I implemented 
a (trivial) cache for the last-searched PC, as well as another (more 
convoluted) for the last-searched symbol. The symbol cache patch gives 
this profile:
   http://jeanmarc.saffroy.free.fr/gdb/gdb-symcache.html
With both patches applied:
   http://jeanmarc.saffroy.free.fr/gdb/gdb-symcache-pc_cache.html

On a regular build (no profiling), my script now runs in 23 seconds 
instead of 158. :-)

This is still unfinished (hooks for invalidating the caches are missing, 
and I'm sure performance can still be enhanced significantly), but before 
going further, I'd like to know how you feel about integrating such 
changes.


Cheers,

-- 
saffroy@gmail.com

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 */

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