RFA: shrink minimal symbols

[Tom Tromey <tromey at redhat dot com>]

This patch shrinks minimal symbols and reimplements the minimal symbol
hash tables.

I added some minimal symbol table statistics printing (not included in
this patch), and then I examined a number of objects by connecting to
them with gdb's 'file' command.

In particular I looked at every executable in /usr/bin on my F8 box,
libgcj.so (perhaps the worst case -- 88582 minsyms, almost all
demangleable) and I also attached to running firefox and a running
soffice.

I found that, in most cases, the demangled hash table was either
completely empty, or had notably fewer entries than the
linkage-name-based table.

This patch reduces memory use by removing the link fields from minimal
symbols.

I modified both the mangled- and demangled hash tables for simplicity
of implementation.  Also, open addressed hashes are preferable, IMO,
when the number of entries is large, because they bound the average
number of searches better.  This may imply a slightly increase of
memory use versus the optimum possible, in some cases.

This hash table is based on having a power-of-two table size.  I tried
a prime-sized table (duplicating some code from hashtab.c) but this
didn't make a big difference.

I looked at the space used by gdb after startup.  This emphasizes the
amount of space used by minimal symbols.  (This isn't an ideal
measurement but, I think, is good enough for this purpose.)

I consistently see memory reductions of 4-8%.  Some figures:

    Program    Before    After       %

    OO.o       73490432  70692864  3.8
    firefox    35336192  32542720  7.9
    libgcj     15466496  14970880  3.2

Built and regtested on x86-64 (compile farm).
Ok?

Tom

:ADDPATCH symbols:

2008-08-27  Tom Tromey  <tromey@redhat.com>

	* symtab.h (struct minimal_symbol) <hash_next,
	demangled_hash_next>: Remove.
	(add_minsym_to_hash_table): Don't declare.
	(delete_minsym_hash): Declare.
	* symfile.c (reread_symbols): Call delete_minsym_hash.
	* objfiles.h (MINIMAL_SYMBOL_HASH_SIZE): Remove.
	(struct objfile) <msymbol_hash, msymbol_demangled_hash>: Change
	type.
	* objfiles.c (free_objfile): Call delete_minsym_hash.
	* minsyms.c (COMPUTE_INDEX): New macro.
	(COMPUTE_HASH2): Likewise.
	(UPDATE_INDEX): Likewise.
	(struct minimal_symbol_hash_table): New struct.
	(new_minsym_hash): New function.
	(delete_minsym_hash): Likewise.
	(find_minsym_hash_slot): Likewise.
	(minsym_hash_expand): Likewise.
	(clear_minsym_hash_table): Likewise.
	(add_minsym_to_hash_table): Rewrite.  Add is_demangled argument.
	Now static.
	(add_minsym_to_demangled_hash_table): Remove.
	(msymbol_objfile, lookup_minimal_symbol,
	lookup_minimal_symbol_text, lookup_minimal_symbol_by_pc_name,
	lookup_minimal_symbol_solib_trampoline,
	prim_record_minimal_symbol_and_info): Update.
	(build_minimal_symbol_hash_tables): Update.  Lazily create
	demangled hash.

diff --git a/gdb/minsyms.c b/gdb/minsyms.c
index 34bbbb9..37672fe 100644
--- a/gdb/minsyms.c
+++ b/gdb/minsyms.c
@@ -74,6 +74,165 @@ static int msym_bunch_index;
 
 static int msym_count;
 
+/* Given a hash code and a table size, compute the initial index into
+   the table.  */
+
+#define COMPUTE_INDEX(HASH, SIZE)  ((HASH) & ((SIZE) - 1))
+
+/* Given a hash code and a table size, compute the second hash code
+   (the step) used for iterating through the table.  Note that the
+   result must be odd, to ensure that we visit all the slots in the
+   table.  */
+
+#define COMPUTE_HASH2(HASH, SIZE) ((((HASH) * 17) & ((SIZE) - 1)) | 1)
+
+/* Given an index into a hash table, the second hash code, and the
+   table size, compute the index of the next slot to visit when
+   iterating through the table.  */
+
+#define UPDATE_INDEX(INDEX, HASH2, SIZE) (((INDEX) + (HASH2)) & ((SIZE) - 1))
+
+/* A hash table for minimal symbols.  */
+
+struct minimal_symbol_hash_table
+{
+  /* Number of occupied slots in the table.  */
+  size_t n_elements;
+
+  /* The total number of slots in the table.  This must be a power of
+     two.  */
+  size_t size;
+
+  /* The entries in the table.  */
+  struct minimal_symbol **entries;
+};
+
+/* Create a new minimal symbol hash table.  N_ELEMENTS_GUESS is used
+   to compute the initial table size; it should be the number of
+   expected entries in the table.  If this is not known, use 1.  The
+   returned hash table can be deallocated using
+   delete_minsym_hash.  */
+
+static struct minimal_symbol_hash_table *
+new_minsym_hash (unsigned int n_elements_guess)
+{
+  struct minimal_symbol_hash_table *result;
+  unsigned int i;
+
+  n_elements_guess = 4 * n_elements_guess / 3 + 1;
+  for (i = 1; i && i < n_elements_guess; i <<= 1)
+    ;
+
+  result = XNEW (struct minimal_symbol_hash_table);
+  result->size = i;
+  result->entries = XCNEWVEC (struct minimal_symbol *, result->size);
+  result->n_elements = 0;
+
+  return result;
+}
+
+/* Free all the memory associated with TABLE.  */
+
+void
+delete_minsym_hash (struct minimal_symbol_hash_table *table)
+{
+  if (table)
+    {
+      xfree (table->entries);
+      xfree (table);
+    }
+}
+
+/* A forward declaration is needed due to mutual recursion.  */
+
+static void minsym_hash_expand (struct minimal_symbol_hash_table *table,
+				int is_demangled);
+
+/* Find the slot for the minimal symbol MINSYM in the hash table
+   TABLE.  If MINSYM appears in the table, its slot is returned.  If
+   it does not appear in the table, an empty slot is returned.
+   IS_DEMANGLED is true if the hash table hashes on demangled entries;
+   false if it hashes on linkage names.  */
+
+static struct minimal_symbol **
+find_minsym_hash_slot (struct minimal_symbol_hash_table *table,
+		       struct minimal_symbol *minsym,
+		       int is_demangled)
+{
+  unsigned int hash, index, hash2;
+
+  if (is_demangled)
+    hash = msymbol_hash_iw (SYMBOL_SEARCH_NAME (minsym));
+  else
+    hash = msymbol_hash (SYMBOL_LINKAGE_NAME (minsym));
+
+  index = COMPUTE_INDEX (hash, table->size);
+  if (!table->entries[index] || table->entries[index] == minsym)
+    return &table->entries[index];
+
+  hash2 = COMPUTE_HASH2 (hash, table->size);
+  for (;;)
+    {
+      index = UPDATE_INDEX (index, hash2, table->size);
+
+      if (!table->entries[index] || table->entries[index] == minsym)
+	return &table->entries[index];
+    }
+}
+
+/* Add the minimal symbol MINSYM to the hash table TABLE.
+   IS_DEMANGLED is true if the hash table hashes on demangled entries;
+   false if it hashes on linkage names.  */
+
+static void
+add_minsym_to_hash_table (struct minimal_symbol_hash_table *table,
+			  struct minimal_symbol *minsym,
+			  int is_demangled)
+{
+  struct minimal_symbol **slot;
+
+  ++table->n_elements;
+  if (4 * table->n_elements / 3 >= table->size)
+    minsym_hash_expand (table, is_demangled);
+
+  slot = find_minsym_hash_slot (table, minsym, is_demangled);
+  *slot = minsym;
+}
+
+/* Expand the hash table TABLE.  IS_DEMANGLED is true if the hash
+   table hashes on demangled entries; false if it hashes on linkage
+   names.  */
+
+static void
+minsym_hash_expand (struct minimal_symbol_hash_table *table, int is_demangled)
+{
+  unsigned int i;
+  unsigned int old_size = table->size;
+  struct minimal_symbol **old_entries = table->entries;
+
+  table->size *= 2;
+  gdb_assert (table->size);
+
+  table->entries = XCNEWVEC (struct minimal_symbol *, table->size);
+  table->n_elements = 0;
+
+  for (i = 0; i < old_size; ++i)
+    if (old_entries[i])
+      add_minsym_to_hash_table (table, old_entries[i], is_demangled);
+
+  xfree (old_entries);
+}
+
+/* Empty the hash table TABLE, but do not free the memory it holds.
+   This is used when rebuilding the minimal symbol tables.  */
+
+static void
+clear_minsym_hash_table (struct minimal_symbol_hash_table *table)
+{
+  table->n_elements = 0;
+  memset (table->entries, 0, table->size * sizeof (struct minimal_symbol *));
+}
+
 /* Compute a hash code based using the same criteria as `strcmp_iw'.  */
 
 unsigned int
@@ -104,50 +263,20 @@ msymbol_hash (const char *string)
   return hash;
 }
 
-/* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE.  */
-void
-add_minsym_to_hash_table (struct minimal_symbol *sym,
-			  struct minimal_symbol **table)
-{
-  if (sym->hash_next == NULL)
-    {
-      unsigned int hash
-	= msymbol_hash (SYMBOL_LINKAGE_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
-      sym->hash_next = table[hash];
-      table[hash] = sym;
-    }
-}
-
-/* Add the minimal symbol SYM to an objfile's minsym demangled hash table,
-   TABLE.  */
-static void
-add_minsym_to_demangled_hash_table (struct minimal_symbol *sym,
-                                  struct minimal_symbol **table)
-{
-  if (sym->demangled_hash_next == NULL)
-    {
-      unsigned int hash
-	= msymbol_hash_iw (SYMBOL_SEARCH_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
-      sym->demangled_hash_next = table[hash];
-      table[hash] = sym;
-    }
-}
-
 
 /* Return OBJFILE where minimal symbol SYM is defined.  */
 struct objfile *
 msymbol_objfile (struct minimal_symbol *sym)
 {
   struct objfile *objf;
-  struct minimal_symbol *tsym;
-
-  unsigned int hash
-    = msymbol_hash (SYMBOL_LINKAGE_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
 
   for (objf = object_files; objf; objf = objf->next)
-    for (tsym = objf->msymbol_hash[hash]; tsym; tsym = tsym->hash_next)
-      if (tsym == sym)
+    {
+      struct minimal_symbol **slot = find_minsym_hash_slot (objf->msymbol_hash,
+							    sym, 0);
+      if (*slot == sym)
 	return objf;
+    }
 
   /* We should always be able to find the objfile ...  */
   internal_error (__FILE__, __LINE__, _("failed internal consistency check"));
@@ -184,8 +313,8 @@ lookup_minimal_symbol (const char *name, const char *sfile,
   struct minimal_symbol *found_file_symbol = NULL;
   struct minimal_symbol *trampoline_symbol = NULL;
 
-  unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
-  unsigned int dem_hash = msymbol_hash_iw (name) % MINIMAL_SYMBOL_HASH_SIZE;
+  unsigned int hash = msymbol_hash (name);
+  unsigned int dem_hash = msymbol_hash_iw (name);
 
   if (sfile != NULL)
     {
@@ -206,17 +335,35 @@ lookup_minimal_symbol (const char *name, const char *sfile,
         int pass;
 
         for (pass = 1; pass <= 2 && found_symbol == NULL; pass++)
-	    {
+	  {
+	    struct minimal_symbol_hash_table *table;
+	    unsigned int this_hash, index, hash2;
+
             /* Select hash list according to pass.  */
             if (pass == 1)
-              msymbol = objfile->msymbol_hash[hash];
+	      {
+		table = objfile->msymbol_hash;
+		this_hash = hash;
+	      }
             else
-              msymbol = objfile->msymbol_demangled_hash[dem_hash];
+	      {
+		table = objfile->msymbol_demangled_hash;
+		this_hash = dem_hash;
+	      }
+
+	    if (!table)
+	      continue;
+
+	    index = COMPUTE_INDEX (this_hash, table->size);
+	    hash2 = COMPUTE_HASH2 (this_hash, table->size);
 
-            while (msymbol != NULL && found_symbol == NULL)
+            while (found_symbol == NULL)
 		{
 		  int match;
 
+		  msymbol = table->entries[index];
+		  if (!msymbol)
+		    break;
 		  if (pass == 1)
 		    match = strcmp (SYMBOL_LINKAGE_NAME (msymbol), name) == 0;
 		  else
@@ -251,10 +398,7 @@ lookup_minimal_symbol (const char *name, const char *sfile,
 		    }
 
                 /* Find the next symbol on the hash chain.  */
-                if (pass == 1)
-                  msymbol = msymbol->hash_next;
-                else
-                  msymbol = msymbol->demangled_hash_next;
+		index = UPDATE_INDEX (index, hash2, table->size);
 		}
 	    }
 	}
@@ -288,8 +432,9 @@ lookup_minimal_symbol_text (const char *name, struct objfile *objf)
   struct minimal_symbol *msymbol;
   struct minimal_symbol *found_symbol = NULL;
   struct minimal_symbol *found_file_symbol = NULL;
+  unsigned int index, hash2;
 
-  unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+  unsigned int hash = msymbol_hash (name);
 
   for (objfile = object_files;
        objfile != NULL && found_symbol == NULL;
@@ -298,10 +443,19 @@ lookup_minimal_symbol_text (const char *name, struct objfile *objf)
       if (objf == NULL || objf == objfile
 	  || objf->separate_debug_objfile == objfile)
 	{
-	  for (msymbol = objfile->msymbol_hash[hash];
-	       msymbol != NULL && found_symbol == NULL;
-	       msymbol = msymbol->hash_next)
+	  unsigned int index, hash2;
+	  struct minimal_symbol_hash_table *table = objfile->msymbol_hash;
+
+	  if (!table)
+	    continue;
+	  index = COMPUTE_INDEX (hash, table->size);
+	  hash2 = COMPUTE_HASH2 (hash, table->size);
+
+	  while (found_symbol == NULL)
 	    {
+	      msymbol = table->entries[index];
+	      if (!msymbol)
+		break;
 	      if (strcmp (SYMBOL_LINKAGE_NAME (msymbol), name) == 0 &&
 		  (MSYMBOL_TYPE (msymbol) == mst_text ||
 		   MSYMBOL_TYPE (msymbol) == mst_file_text))
@@ -316,6 +470,7 @@ lookup_minimal_symbol_text (const char *name, struct objfile *objf)
 		      break;
 		    }
 		}
+	      index = UPDATE_INDEX (index, hash2, table->size);
 	    }
 	}
     }
@@ -342,7 +497,7 @@ lookup_minimal_symbol_by_pc_name (CORE_ADDR pc, const char *name,
   struct objfile *objfile;
   struct minimal_symbol *msymbol;
 
-  unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+  unsigned int hash = msymbol_hash (name);
 
   for (objfile = object_files;
        objfile != NULL;
@@ -351,13 +506,23 @@ lookup_minimal_symbol_by_pc_name (CORE_ADDR pc, const char *name,
       if (objf == NULL || objf == objfile
 	  || objf->separate_debug_objfile == objfile)
 	{
-	  for (msymbol = objfile->msymbol_hash[hash];
-	       msymbol != NULL;
-	       msymbol = msymbol->hash_next)
+	  unsigned int index, hash2;
+	  struct minimal_symbol_hash_table *table = objfile->msymbol_hash;
+
+	  if (!table)
+	    continue;
+	  index = COMPUTE_INDEX (hash, table->size);
+	  hash2 = COMPUTE_HASH2 (hash, table->size);
+
+	  for (;;)
 	    {
+	      msymbol = table->entries[index];
+	      if (!msymbol)
+		break;
 	      if (SYMBOL_VALUE_ADDRESS (msymbol) == pc
 		  && strcmp (SYMBOL_LINKAGE_NAME (msymbol), name) == 0)
 		return msymbol;
+	      index = UPDATE_INDEX (index, hash2, table->size);
 	    }
 	}
     }
@@ -381,7 +546,7 @@ lookup_minimal_symbol_solib_trampoline (const char *name,
   struct minimal_symbol *msymbol;
   struct minimal_symbol *found_symbol = NULL;
 
-  unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+  unsigned int hash = msymbol_hash (name);
 
   for (objfile = object_files;
        objfile != NULL && found_symbol == NULL;
@@ -390,13 +555,23 @@ lookup_minimal_symbol_solib_trampoline (const char *name,
       if (objf == NULL || objf == objfile
 	  || objf->separate_debug_objfile == objfile)
 	{
-	  for (msymbol = objfile->msymbol_hash[hash];
-	       msymbol != NULL && found_symbol == NULL;
-	       msymbol = msymbol->hash_next)
+	  unsigned int index, hash2;
+	  struct minimal_symbol_hash_table *table = objfile->msymbol_hash;
+
+	  if (!table)
+	    continue;
+	  index = COMPUTE_INDEX (hash, table->size);
+	  hash2 = COMPUTE_HASH2 (hash, table->size);
+
+	  while (found_symbol == NULL)
 	    {
+	      msymbol = table->entries[index];
+	      if (!msymbol)
+		break;
 	      if (strcmp (SYMBOL_LINKAGE_NAME (msymbol), name) == 0 &&
 		  MSYMBOL_TYPE (msymbol) == mst_solib_trampoline)
 		return msymbol;
+	      index = UPDATE_INDEX (index, hash2, table->size);
 	    }
 	}
     }
@@ -779,11 +954,6 @@ prim_record_minimal_symbol_and_info (const char *name, CORE_ADDR address,
   MSYMBOL_INFO (msymbol) = info;	/* FIXME! */
   MSYMBOL_SIZE (msymbol) = 0;
 
-  /* The hash pointers must be cleared! If they're not,
-     add_minsym_to_hash_table will NOT add this msymbol to the hash table. */
-  msymbol->hash_next = NULL;
-  msymbol->demangled_hash_next = NULL;
-
   msym_bunch_index++;
   msym_count++;
   OBJSTAT (objfile, n_minsyms++);
@@ -934,26 +1104,36 @@ build_minimal_symbol_hash_tables (struct objfile *objfile)
 {
   int i;
   struct minimal_symbol *msym;
+  struct minimal_symbol_hash_table *demangled_table;
 
-  /* Clear the hash tables. */
-  for (i = 0; i < MINIMAL_SYMBOL_HASH_SIZE; i++)
-    {
-      objfile->msymbol_hash[i] = 0;
-      objfile->msymbol_demangled_hash[i] = 0;
-    }
+  /* Clear or create the hash table. */
+  if (objfile->msymbol_hash)
+    clear_minsym_hash_table (objfile->msymbol_hash);
+  else
+    objfile->msymbol_hash = new_minsym_hash (objfile->minimal_symbol_count);
+
+  /* We create the demangled table on demand, because in many cases
+     there is no need for it at all.  */
+  demangled_table = objfile->msymbol_demangled_hash;
+  if (demangled_table)
+    clear_minsym_hash_table (demangled_table);
 
   /* Now, (re)insert the actual entries. */
   for (i = objfile->minimal_symbol_count, msym = objfile->msymbols;
        i > 0;
        i--, msym++)
     {
-      msym->hash_next = 0;
-      add_minsym_to_hash_table (msym, objfile->msymbol_hash);
+      add_minsym_to_hash_table (objfile->msymbol_hash, msym, 0);
 
-      msym->demangled_hash_next = 0;
       if (SYMBOL_SEARCH_NAME (msym) != SYMBOL_LINKAGE_NAME (msym))
-	add_minsym_to_demangled_hash_table (msym,
-                                            objfile->msymbol_demangled_hash);
+	{
+	  if (!demangled_table)
+	    {
+	      demangled_table = new_minsym_hash (1);
+	      objfile->msymbol_demangled_hash = demangled_table;
+	    }
+	  add_minsym_to_hash_table (demangled_table, msym, 1);
+	}
     }
 }
 
diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index 16be84a..bfe1878 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -474,6 +474,9 @@ free_objfile (struct objfile *objfile)
       }
   }
 
+  delete_minsym_hash (objfile->msymbol_hash);
+  delete_minsym_hash (objfile->msymbol_demangled_hash);
+
   /* The last thing we do is free the objfile struct itself. */
 
   objfile_free_data (objfile);
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index d98eabb..bb23ac8 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -160,9 +160,6 @@ struct objstats
 extern void print_objfile_statistics (void);
 extern void print_symbol_bcache_statistics (void);
 
-/* Number of entries in the minimal symbol hash table.  */
-#define MINIMAL_SYMBOL_HASH_SIZE 2039
-
 /* Master structure for keeping track of each file from which
    gdb reads symbols.  There are several ways these get allocated: 1.
    The main symbol file, symfile_objfile, set by the symbol-file command,
@@ -278,12 +275,12 @@ struct objfile
 
     /* This is a hash table used to index the minimal symbols by name.  */
 
-    struct minimal_symbol *msymbol_hash[MINIMAL_SYMBOL_HASH_SIZE];
+    struct minimal_symbol_hash_table *msymbol_hash;
 
     /* This hash table is used to index the minimal symbols by their
        demangled names.  */
 
-    struct minimal_symbol *msymbol_demangled_hash[MINIMAL_SYMBOL_HASH_SIZE];
+    struct minimal_symbol_hash_table *msymbol_demangled_hash;
 
     /* Structure which keeps track of functions that manipulate objfile's
        of the same type as this objfile.  I.E. the function to read partial
diff --git a/gdb/symfile.c b/gdb/symfile.c
index faa375b..8120df0 100644
--- a/gdb/symfile.c
+++ b/gdb/symfile.c
@@ -2361,10 +2361,12 @@ reread_symbols (void)
 	      objfile->msymbols = NULL;
 	      objfile->deprecated_sym_private = NULL;
 	      objfile->minimal_symbol_count = 0;
-	      memset (&objfile->msymbol_hash, 0,
-		      sizeof (objfile->msymbol_hash));
-	      memset (&objfile->msymbol_demangled_hash, 0,
-		      sizeof (objfile->msymbol_demangled_hash));
+
+	      delete_minsym_hash (objfile->msymbol_hash);
+	      objfile->msymbol_hash = NULL;
+	      delete_minsym_hash (objfile->msymbol_demangled_hash);
+	      objfile->msymbol_demangled_hash = NULL;
+
 	      clear_objfile_data (objfile);
 	      if (objfile->sf != NULL)
 		{
diff --git a/gdb/symtab.h b/gdb/symtab.h
index 31aed86..20b3d9a 100644
--- a/gdb/symtab.h
+++ b/gdb/symtab.h
@@ -346,16 +346,6 @@ struct minimal_symbol
   /* Classification type for this minimal symbol.  */
 
   ENUM_BITFIELD(minimal_symbol_type) type : 8;
-
-  /* Minimal symbols with the same hash key are kept on a linked
-     list.  This is the link.  */
-
-  struct minimal_symbol *hash_next;
-
-  /* Minimal symbols are stored in two different hash tables.  This is
-     the `next' pointer for the demangled hash table.  */
-
-  struct minimal_symbol *demangled_hash_next;
 };
 
 #define MSYMBOL_INFO(msymbol)		(msymbol)->info
@@ -1106,9 +1096,9 @@ extern unsigned int msymbol_hash (const char *);
 
 extern struct objfile * msymbol_objfile (struct minimal_symbol *sym);
 
-extern void
-add_minsym_to_hash_table (struct minimal_symbol *sym,
-			  struct minimal_symbol **table);
+struct minimal_symbol_hash_table;
+
+extern void delete_minsym_hash (struct minimal_symbol_hash_table *);
 
 extern struct minimal_symbol *lookup_minimal_symbol (const char *,
 						     const char *,