[commit/Ada] Add a symbol lookup cache

[commit/Ada] Add a symbol lookup cache

[Joel Brobecker]

Hello,

This patch implements the caching mechanism alluded to in a comment
next to some stubbed functions.

gdb/ChangeLog:

        * ada-lang.c (HASH_SIZE): New macro.
        (struct cache_entry): New type.
        (cache_space, cache): New static globals.
        (ada_clear_symbol_cache, find_entry): New functions.
        (lookup_cached_symbol, cache_symbol): Implement.
        (ada_new_objfile_observer, ada_free_objfile_observer): New.
        (_initialize_ada_language): Attach ada_new_objfile_observer
        and ada_free_objfile_observer.

Tested on x86_64-linux and pushed.

Thanks,
-- 
Joel

---
 gdb/ChangeLog  |  11 +++++
 gdb/ada-lang.c | 135 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 143 insertions(+), 3 deletions(-)

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 940c6a2..828cb6e 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,5 +1,16 @@
 2014-02-10  Joel Brobecker  <brobecker@adacore.com>
 
+	* ada-lang.c (HASH_SIZE): New macro.
+	(struct cache_entry): New type.
+	(cache_space, cache): New static globals.
+	(ada_clear_symbol_cache, find_entry): New functions.
+	(lookup_cached_symbol, cache_symbol): Implement.
+	(ada_new_objfile_observer, ada_free_objfile_observer): New.
+	(_initialize_ada_language): Attach ada_new_objfile_observer
+	and ada_free_objfile_observer.
+
+2014-02-10  Joel Brobecker  <brobecker@adacore.com>
+
 	* ada-lang.c (ada_add_block_symbols, add_defn_to_vec)
 	(lookup_cached_symbol, ada_add_local_symbols): Add "const" to
 	struct block * parameter.
diff --git a/gdb/ada-lang.c b/gdb/ada-lang.c
index 269112c..fc2c83b 100644
--- a/gdb/ada-lang.c
+++ b/gdb/ada-lang.c
@@ -4245,20 +4245,129 @@ make_array_descriptor (struct type *type, struct value *arr)
     return descriptor;
 }
 \f
-/* Dummy definitions for an experimental caching module that is not
- * used in the public sources.  */
+                                /* Symbol Cache Module */
+
+/* This section implements a simple, fixed-sized hash table for those
+   Ada-mode symbols that get looked up in the course of executing the user's
+   commands.  The size is fixed on the grounds that there are not
+   likely to be all that many symbols looked up during any given
+   session, regardless of the size of the symbol table.  If we decide
+   to go to a resizable table, let's just use the stuff from libiberty
+   instead.  */
+
+/* Performance measurements made as of 2010-01-15 indicate that
+   this case does bring some noticeable improvements.  Depending
+   on the type of entity being printed, the cache can make it as much
+   as an order of magnitude faster than without it.
+
+   The descriptive type DWARF extension has significantly reduced
+   the need for this cache, at least when DWARF is being used.  However,
+   even in this case, some expensive name-based symbol searches are still
+   sometimes necessary - to find an XVZ variable, mostly.  */
+
+#define HASH_SIZE 1009
+
+/* The result of a symbol lookup to be stored in our cache.  */
+
+struct cache_entry
+{
+  /* The name used to perform the lookup.  */
+  const char *name;
+  /* The namespace used during the lookup.  */
+  domain_enum namespace;
+  /* The symbol returned by the lookup, or NULL if no matching symbol
+     was found.  */
+  struct symbol *sym;
+  /* The block where the symbol was found, or NULL if no matching
+     symbol was found.  */
+  const struct block *block;
+  /* A pointer to the next entry with the same hash.  */
+  struct cache_entry *next;
+};
+
+/* An obstack used to store the entries in our cache.  */
+static struct obstack cache_space;
+
+/* The root of the hash table used to implement our symbol cache.  */
+static struct cache_entry *cache[HASH_SIZE];
+
+/* Clear all entries from the symbol cache.  */
+
+static void
+ada_clear_symbol_cache (void)
+{
+  obstack_free (&cache_space, NULL);
+  obstack_init (&cache_space);
+  memset (cache, '\000', sizeof (cache));
+}
+
+/* Search our cache for an entry matching NAME and NAMESPACE.
+   Return it if found, or NULL otherwise.  */
+
+static struct cache_entry **
+find_entry (const char *name, domain_enum namespace)
+{
+  int h = msymbol_hash (name) % HASH_SIZE;
+  struct cache_entry **e;
+
+  for (e = &cache[h]; *e != NULL; e = &(*e)->next)
+    {
+      if (namespace == (*e)->namespace && strcmp (name, (*e)->name) == 0)
+        return e;
+    }
+  return NULL;
+}
+
+/* Search the symbol cache for an entry matching NAME and NAMESPACE.
+   Return 1 if found, 0 otherwise.
+
+   If an entry was found and SYM is not NULL, set *SYM to the entry's
+   SYM.  Same principle for BLOCK if not NULL.  */
 
 static int
 lookup_cached_symbol (const char *name, domain_enum namespace,
                       struct symbol **sym, const struct block **block)
 {
-  return 0;
+  struct cache_entry **e = find_entry (name, namespace);
+
+  if (e == NULL)
+    return 0;
+  if (sym != NULL)
+    *sym = (*e)->sym;
+  if (block != NULL)
+    *block = (*e)->block;
+  return 1;
 }
 
+/* Assuming that (SYM, BLOCK) is the result of the lookup of NAME
+   in domain NAMESPACE, save this result in our symbol cache.  */
+
 static void
 cache_symbol (const char *name, domain_enum namespace, struct symbol *sym,
               const struct block *block)
 {
+  int h;
+  char *copy;
+  struct cache_entry *e;
+
+  /* If the symbol is a local symbol, then do not cache it, as a search
+     for that symbol depends on the context.  To determine whether
+     the symbol is local or not, we check the block where we found it
+     against the global and static blocks of its associated symtab.  */
+  if (sym
+      && BLOCKVECTOR_BLOCK (BLOCKVECTOR (sym->symtab), GLOBAL_BLOCK) != block
+      && BLOCKVECTOR_BLOCK (BLOCKVECTOR (sym->symtab), STATIC_BLOCK) != block)
+    return;
+
+  h = msymbol_hash (name) % HASH_SIZE;
+  e = (struct cache_entry *) obstack_alloc (&cache_space, sizeof (*e));
+  e->next = cache[h];
+  cache[h] = e;
+  e->name = copy = obstack_alloc (&cache_space, strlen (name) + 1);
+  strcpy (copy, name);
+  e->sym = sym;
+  e->namespace = namespace;
+  e->block = block;
 }
 \f
                                 /* Symbol Lookup */
@@ -13295,6 +13404,22 @@ initialize_ada_catchpoint_ops (void)
   ops->print_recreate = print_recreate_catch_assert;
 }
 
+/* This module's 'new_objfile' observer.  */
+
+static void
+ada_new_objfile_observer (struct objfile *objfile)
+{
+  ada_clear_symbol_cache ();
+}
+
+/* This module's 'free_objfile' observer.  */
+
+static void
+ada_free_objfile_observer (struct objfile *objfile)
+{
+  ada_clear_symbol_cache ();
+}
+
 void
 _initialize_ada_language (void)
 {
@@ -13373,6 +13498,10 @@ DWARF attribute."),
     (256, htab_hash_string, (int (*)(const void *, const void *)) streq,
      NULL, xcalloc, xfree);
 
+  /* The ada-lang observers.  */
+  observer_attach_new_objfile (ada_new_objfile_observer);
+  observer_attach_free_objfile (ada_free_objfile_observer);
+
   /* Setup per-inferior data.  */
   observer_attach_inferior_exit (ada_inferior_exit);
   ada_inferior_data
-- 
1.8.3.2

Re: [commit/Ada] Add a symbol lookup cache

[Pedro Alves]

On 02/10/2014 07:51 AM, Joel Brobecker wrote:
> +
> +/* An obstack used to store the entries in our cache.  */
> +static struct obstack cache_space;
> +
> +/* The root of the hash table used to implement our symbol cache.  */
> +static struct cache_entry *cache[HASH_SIZE];

Seems to me this should be per program space, not global?

-- 
Pedro Alves

Re: [commit/Ada] Add a symbol lookup cache

[Joel Brobecker]

> > +/* An obstack used to store the entries in our cache.  */
> > +static struct obstack cache_space;
> > +
> > +/* The root of the hash table used to implement our symbol cache.  */
> > +static struct cache_entry *cache[HASH_SIZE];
> 
> Seems to me this should be per program space, not global?

You're right. I'm in the middle of testing the DLL load/unload
cleanup patches, but I will take care of it right after.

Thanks,
-- 
Joel

Re: [commit/Ada] Add a symbol lookup cache

[Joel Brobecker]

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

> > > +static struct obstack cache_space;
> > > +
> > > +/* The root of the hash table used to implement our symbol cache.  */
> > > +static struct cache_entry *cache[HASH_SIZE];
> > 
> > Seems to me this should be per program space, not global?
> 
> You're right. I'm in the middle of testing the DLL load/unload
> cleanup patches, but I will take care of it right after.

I thought I was going to be done in under an hour, but not so fast,
after all...

Attached is what I ended checking in.

gdb/ChangeLog:

        * ada-lang.c (struct cache_entry, HASH_SIZE): Move definition up.
        (struct ada_symbol_cache): New.
        (ada_free_symbol_cache): Forward declare.
        (struct ada_pspace_data): New.
        (ada_pspace_data_handle): New static global.
        (get_ada_pspace_data, ada_pspace_data_cleanup)
        (ada_init_symbol_cache, ada_free_symbol_cache): New functions.
        (cache_space, cache): Delete, now folded inside struct
        ada_pspace_data.
        (ada_get_symbol_cache): New function.
        (ada_clear_symbol_cache, find_entry, cache_symbol): Adjust
        implementation.
        (_initialize_ada_language): Remove initialization of cache_space.
        Move call to observer_attach_inferior_exit up, grouping it
        with the other observer registrations inside this function.
        Rename command to be more general.  Add call to
        register_program_space_data_with_cleanup.

Tested on x86_64-linux, no regression.  Pushed.

Thanks for the nudge...
-- 
Joel

[-- Attachment #2: 0001-Ada-Make-the-symbol-cache-per-program-space.patch --]
[-- Type: text/x-diff, Size: 11428 bytes --]

From ee01b6652ad55437e777fb7e6b1745782dc205a4 Mon Sep 17 00:00:00 2001
From: Joel Brobecker <brobecker@adacore.com>
Date: Mon, 10 Feb 2014 17:49:27 +0400
Subject: [PATCH] [Ada] Make the symbol cache per-program-space.

This patch moves the Ada symbol cache to per-program-space data.

gdb/ChangeLog:

        * ada-lang.c (struct cache_entry, HASH_SIZE): Move definition up.
        (struct ada_symbol_cache): New.
        (ada_free_symbol_cache): Forward declare.
        (struct ada_pspace_data): New.
        (ada_pspace_data_handle): New static global.
        (get_ada_pspace_data, ada_pspace_data_cleanup)
        (ada_init_symbol_cache, ada_free_symbol_cache): New functions.
        (cache_space, cache): Delete, now folded inside struct
        ada_pspace_data.
        (ada_get_symbol_cache): New function.
        (ada_clear_symbol_cache, find_entry, cache_symbol): Adjust
        implementation.
        (_initialize_ada_language): Remove initialization of cache_space.
        Move call to observer_attach_inferior_exit up, grouping it
        with the other observer registrations inside this function.
        Rename command to be more general.  Add call to
        register_program_space_data_with_cleanup.
---
 gdb/ChangeLog  |  20 +++++++
 gdb/ada-lang.c | 174 ++++++++++++++++++++++++++++++++++++++++++++-------------
 2 files changed, 154 insertions(+), 40 deletions(-)

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index c94a5dd..84e02e4 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,5 +1,25 @@
 2014-02-10  Joel Brobecker  <brobecker@adacore.com>
 
+	* ada-lang.c (struct cache_entry, HASH_SIZE): Move definition up.
+	(struct ada_symbol_cache): New.
+	(ada_free_symbol_cache): Forward declare.
+	(struct ada_pspace_data): New.
+	(ada_pspace_data_handle): New static global.
+	(get_ada_pspace_data, ada_pspace_data_cleanup)
+	(ada_init_symbol_cache, ada_free_symbol_cache): New functions.
+	(cache_space, cache): Delete, now folded inside struct
+	ada_pspace_data.
+	(ada_get_symbol_cache): New function.
+	(ada_clear_symbol_cache, find_entry, cache_symbol): Adjust
+	implementation.
+	(_initialize_ada_language): Remove initialization of cache_space.
+	Move call to observer_attach_inferior_exit up, grouping it
+	with the other observer registrations inside this function.
+	Rename command to be more general.  Add call to
+	register_program_space_data_with_cleanup.
+
+2014-02-10  Joel Brobecker  <brobecker@adacore.com>
+
 	* ada-tasks.c (ada_tasks_new_objfile_observer): Renames
 	ada_new_objfile_observer.
 	(ada_tasks_normal_stop_observer): Renames ada_normal_stop_observer.
diff --git a/gdb/ada-lang.c b/gdb/ada-lang.c
index e69ed81..a10d800 100644
--- a/gdb/ada-lang.c
+++ b/gdb/ada-lang.c
@@ -273,6 +273,45 @@ static void ada_forward_operator_length (struct expression *, int, int *,
 static struct type *ada_find_any_type (const char *name);
 \f
 
+/* The result of a symbol lookup to be stored in our symbol cache.  */
+
+struct cache_entry
+{
+  /* The name used to perform the lookup.  */
+  const char *name;
+  /* The namespace used during the lookup.  */
+  domain_enum namespace;
+  /* The symbol returned by the lookup, or NULL if no matching symbol
+     was found.  */
+  struct symbol *sym;
+  /* The block where the symbol was found, or NULL if no matching
+     symbol was found.  */
+  const struct block *block;
+  /* A pointer to the next entry with the same hash.  */
+  struct cache_entry *next;
+};
+
+/* The Ada symbol cache, used to store the result of Ada-mode symbol
+   lookups in the course of executing the user's commands.
+
+   The cache is implemented using a simple, fixed-sized hash.
+   The size is fixed on the grounds that there are not likely to be
+   all that many symbols looked up during any given session, regardless
+   of the size of the symbol table.  If we decide to go to a resizable
+   table, let's just use the stuff from libiberty instead.  */
+
+#define HASH_SIZE 1009
+
+struct ada_symbol_cache
+{
+  /* An obstack used to store the entries in our cache.  */
+  struct obstack cache_space;
+
+  /* The root of the hash table used to implement our symbol cache.  */
+  struct cache_entry *root[HASH_SIZE];
+};
+
+static void ada_free_symbol_cache (struct ada_symbol_cache *sym_cache);
 
 /* Maximum-sized dynamic type.  */
 static unsigned int varsize_limit;
@@ -398,6 +437,51 @@ ada_inferior_exit (struct inferior *inf)
   set_inferior_data (inf, ada_inferior_data, NULL);
 }
 
+
+			/* program-space-specific data.  */
+
+/* This module's per-program-space data.  */
+struct ada_pspace_data
+{
+  /* The Ada symbol cache.  */
+  struct ada_symbol_cache *sym_cache;
+};
+
+/* Key to our per-program-space data.  */
+static const struct program_space_data *ada_pspace_data_handle;
+
+/* Return this module's data for the given program space (PSPACE).
+   If not is found, add a zero'ed one now.
+
+   This function always returns a valid object.  */
+
+static struct ada_pspace_data *
+get_ada_pspace_data (struct program_space *pspace)
+{
+  struct ada_pspace_data *data;
+
+  data = program_space_data (pspace, ada_pspace_data_handle);
+  if (data == NULL)
+    {
+      data = XCNEW (struct ada_pspace_data);
+      set_program_space_data (pspace, ada_pspace_data_handle, data);
+    }
+
+  return data;
+}
+
+/* The cleanup callback for this module's per-program-space data.  */
+
+static void
+ada_pspace_data_cleanup (struct program_space *pspace, void *data)
+{
+  struct ada_pspace_data *pspace_data = data;
+
+  if (pspace_data->sym_cache != NULL)
+    ada_free_symbol_cache (pspace_data->sym_cache);
+  xfree (pspace_data);
+}
+
                         /* Utilities */
 
 /* If TYPE is a TYPE_CODE_TYPEDEF type, return the target type after
@@ -4247,16 +4331,8 @@ make_array_descriptor (struct type *type, struct value *arr)
 \f
                                 /* Symbol Cache Module */
 
-/* This section implements a simple, fixed-sized hash table for those
-   Ada-mode symbols that get looked up in the course of executing the user's
-   commands.  The size is fixed on the grounds that there are not
-   likely to be all that many symbols looked up during any given
-   session, regardless of the size of the symbol table.  If we decide
-   to go to a resizable table, let's just use the stuff from libiberty
-   instead.  */
-
 /* Performance measurements made as of 2010-01-15 indicate that
-   this case does bring some noticeable improvements.  Depending
+   this cache does bring some noticeable improvements.  Depending
    on the type of entity being printed, the cache can make it as much
    as an order of magnitude faster than without it.
 
@@ -4265,40 +4341,52 @@ make_array_descriptor (struct type *type, struct value *arr)
    even in this case, some expensive name-based symbol searches are still
    sometimes necessary - to find an XVZ variable, mostly.  */
 
-#define HASH_SIZE 1009
+/* Initialize the contents of SYM_CACHE.  */
 
-/* The result of a symbol lookup to be stored in our cache.  */
+static void
+ada_init_symbol_cache (struct ada_symbol_cache *sym_cache)
+{
+  obstack_init (&sym_cache->cache_space);
+  memset (sym_cache->root, '\000', sizeof (sym_cache->root));
+}
 
-struct cache_entry
+/* Free the memory used by SYM_CACHE.  */
+
+static void
+ada_free_symbol_cache (struct ada_symbol_cache *sym_cache)
 {
-  /* The name used to perform the lookup.  */
-  const char *name;
-  /* The namespace used during the lookup.  */
-  domain_enum namespace;
-  /* The symbol returned by the lookup, or NULL if no matching symbol
-     was found.  */
-  struct symbol *sym;
-  /* The block where the symbol was found, or NULL if no matching
-     symbol was found.  */
-  const struct block *block;
-  /* A pointer to the next entry with the same hash.  */
-  struct cache_entry *next;
-};
+  obstack_free (&sym_cache->cache_space, NULL);
+  xfree (sym_cache);
+}
 
-/* An obstack used to store the entries in our cache.  */
-static struct obstack cache_space;
+/* Return the symbol cache associated to the given program space PSPACE.
+   If not allocated for this PSPACE yet, allocate and initialize one.  */
 
-/* The root of the hash table used to implement our symbol cache.  */
-static struct cache_entry *cache[HASH_SIZE];
+static struct ada_symbol_cache *
+ada_get_symbol_cache (struct program_space *pspace)
+{
+  struct ada_pspace_data *pspace_data = get_ada_pspace_data (pspace);
+  struct ada_symbol_cache *sym_cache = pspace_data->sym_cache;
+
+  if (sym_cache == NULL)
+    {
+      sym_cache = XCNEW (struct ada_symbol_cache);
+      ada_init_symbol_cache (sym_cache);
+    }
+
+  return sym_cache;
+}
 
 /* Clear all entries from the symbol cache.  */
 
 static void
 ada_clear_symbol_cache (void)
 {
-  obstack_free (&cache_space, NULL);
-  obstack_init (&cache_space);
-  memset (cache, '\000', sizeof (cache));
+  struct ada_symbol_cache *sym_cache
+    = ada_get_symbol_cache (current_program_space);
+
+  obstack_free (&sym_cache->cache_space, NULL);
+  ada_init_symbol_cache (sym_cache);
 }
 
 /* Search our cache for an entry matching NAME and NAMESPACE.
@@ -4307,10 +4395,12 @@ ada_clear_symbol_cache (void)
 static struct cache_entry **
 find_entry (const char *name, domain_enum namespace)
 {
+  struct ada_symbol_cache *sym_cache
+    = ada_get_symbol_cache (current_program_space);
   int h = msymbol_hash (name) % HASH_SIZE;
   struct cache_entry **e;
 
-  for (e = &cache[h]; *e != NULL; e = &(*e)->next)
+  for (e = &sym_cache->root[h]; *e != NULL; e = &(*e)->next)
     {
       if (namespace == (*e)->namespace && strcmp (name, (*e)->name) == 0)
         return e;
@@ -4346,6 +4436,8 @@ static void
 cache_symbol (const char *name, domain_enum namespace, struct symbol *sym,
               const struct block *block)
 {
+  struct ada_symbol_cache *sym_cache
+    = ada_get_symbol_cache (current_program_space);
   int h;
   char *copy;
   struct cache_entry *e;
@@ -4360,10 +4452,11 @@ cache_symbol (const char *name, domain_enum namespace, struct symbol *sym,
     return;
 
   h = msymbol_hash (name) % HASH_SIZE;
-  e = (struct cache_entry *) obstack_alloc (&cache_space, sizeof (*e));
-  e->next = cache[h];
-  cache[h] = e;
-  e->name = copy = obstack_alloc (&cache_space, strlen (name) + 1);
+  e = (struct cache_entry *) obstack_alloc (&sym_cache->cache_space,
+					    sizeof (*e));
+  e->next = sym_cache->root[h];
+  sym_cache->root[h] = e;
+  e->name = copy = obstack_alloc (&sym_cache->cache_space, strlen (name) + 1);
   strcpy (copy, name);
   e->sym = sym;
   e->namespace = namespace;
@@ -13503,7 +13596,6 @@ DWARF attribute."),
      NULL, NULL, &maint_set_ada_cmdlist, &maint_show_ada_cmdlist);
 
   obstack_init (&symbol_list_obstack);
-  obstack_init (&cache_space);
 
   decoded_names_store = htab_create_alloc
     (256, htab_hash_string, (int (*)(const void *, const void *)) streq,
@@ -13512,9 +13604,11 @@ DWARF attribute."),
   /* The ada-lang observers.  */
   observer_attach_new_objfile (ada_new_objfile_observer);
   observer_attach_free_objfile (ada_free_objfile_observer);
-
-  /* Setup per-inferior data.  */
   observer_attach_inferior_exit (ada_inferior_exit);
+
+  /* Setup various context-specific data.  */
   ada_inferior_data
     = register_inferior_data_with_cleanup (NULL, ada_inferior_data_cleanup);
+  ada_pspace_data_handle
+    = register_program_space_data_with_cleanup (NULL, ada_pspace_data_cleanup);
 }
-- 
1.8.3.2