Re: [patch 1/2] Use custom hash function with bcache [Re: [RFC] Use custom hash function with bcache]

[sami wagiaalla <swagiaal@redhat.com>]

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

Revised patch attached.

[-- Attachment #2: custom_hash_1.patch --]
[-- Type: text/x-patch, Size: 10318 bytes --]

Enable custom bcache hash function.

2010-08-25  Sami Wagiaalla  <swagiaal@redhat.com>

	* psymtab.c (add_psymbol_to_bcache): Remove 'static' from
	'static partial_symbol psymbol'.
	(psymbol_hash): New function.
	(psymbol_compare): New function.
	* bcache.c (hash_continue): New.
	(hash): Use hash_continue.
	* bcache.c: Add hash_function and compare_function
	pointers to bcache struct.
	(bcache_full): Use bcache->hash_function, and
	bcache->compare_function.
	(bcache_compare): New function.
	(bcache_xmalloc): Take hash_function and
	compare_function arguments and initialize the
	bcach's pointers.
	Updated comment.
	* objfiles.c (allocate_objfile): Updated.
	* symfile.c (reread_symbols): Updated.

diff --git a/gdb/bcache.c b/gdb/bcache.c
index 7d9180c..b72bcaf 100644
--- a/gdb/bcache.c
+++ b/gdb/bcache.c
@@ -89,6 +89,12 @@ struct bcache
      16 bits of hash values) hit, but the corresponding combined
      length/data compare missed.  */
   unsigned long half_hash_miss_count;
+
+  /* Hash function to be used for this bcache object.  */
+  unsigned long (*hash_function)(const void *addr, int length);
+
+  /* Compare function to be used for this bcache object.  */
+  int (*compare_function)(const void *, const void *, int length);
 };
 
 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
@@ -98,12 +104,19 @@ struct bcache
 unsigned long
 hash(const void *addr, int length)
 {
+  return hash_continue (addr, length, 0);
+}
+
+/* Continue the calculation of the hash H at the given address.  */
+
+unsigned long
+hash_continue (const void *addr, int length, unsigned long h)
+{
   const unsigned char *k, *e;
-  unsigned long h;
 
   k = (const unsigned char *)addr;
   e = k+length;
-  for (h=0; k< e;++k)
+  for (; k< e;++k)
     {
       h *=16777619;
       h ^= *k;
@@ -235,7 +248,8 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added)
   bcache->total_count++;
   bcache->total_size += length;
 
-  full_hash = hash (addr, length);
+  full_hash = bcache->hash_function (addr, length);
+
   half_hash = (full_hash >> 16);
   hash_index = full_hash % bcache->num_buckets;
 
@@ -247,7 +261,7 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added)
       if (s->half_hash == half_hash)
 	{
 	  if (s->length == length
-	      && ! memcmp (&s->d.data, addr, length))
+	      && bcache->compare_function (&s->d.data, addr, length))
 	    return &s->d.data;
 	  else
 	    bcache->half_hash_miss_count++;
@@ -276,14 +290,39 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added)
   }
 }
 \f
+
+/* Compare the byte string at ADDR1 of lenght LENGHT to the
+   string at ADDR2.  Return 1 if they are equal.  */
+
+static int
+bcache_compare (const void* addr1, const void* addr2, int length)
+{
+  return memcmp (addr1, addr2, length) == 0;
+}
+
 /* Allocating and freeing bcaches.  */
 
+/* Allocated a bcache.  HASH_FUNCTION and COMPARE_FUNCTION can be used
+   to pass in custom hash, and compare functions to be used by this
+   bcache. If HASH_FUNCTION is NULL hash() is used and if COMPARE_FUNCTION
+   is NULL memcmp() is used.  */
+
 struct bcache *
-bcache_xmalloc (void)
+bcache_xmalloc (unsigned long (*hash_function)(const void *, int length),
+                int (*compare_function)(const void *, const void *, int length))
 {
   /* Allocate the bcache pre-zeroed.  */
   struct bcache *b = XCALLOC (1, struct bcache);
 
+  if (hash_function)
+    b->hash_function = hash_function;
+  else
+    b->hash_function = hash;
+
+  if (compare_function)
+    b->compare_function = compare_function;
+  else
+    b->compare_function = bcache_compare;
   return b;
 }
 
diff --git a/gdb/bcache.h b/gdb/bcache.h
index da69a2d..d000962 100644
--- a/gdb/bcache.h
+++ b/gdb/bcache.h
@@ -158,7 +158,9 @@ extern const void *bcache_full (const void *addr, int length,
 extern void bcache_xfree (struct bcache *bcache);
 
 /* Create a new bcache object.  */
-extern struct bcache *bcache_xmalloc (void);
+extern struct bcache *bcache_xmalloc (
+    unsigned long (*hash_function)(const void *, int length),
+    int (*compare_function)(const void *, const void *, int length));
 
 /* Print statistics on BCACHE's memory usage and efficacity at
    eliminating duplication.  TYPE should be a string describing the
@@ -167,7 +169,9 @@ extern struct bcache *bcache_xmalloc (void);
 extern void print_bcache_statistics (struct bcache *bcache, char *type);
 extern int bcache_memory_used (struct bcache *bcache);
 
-/* The hash function */
+/* The hash functions */
 extern unsigned long hash(const void *addr, int length);
+extern unsigned long hash_continue (const void *addr, int length,
+                                    unsigned long h);
 
 #endif /* BCACHE_H */
diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index b522189..c479d22 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -199,9 +199,9 @@ allocate_objfile (bfd *abfd, int flags)
   struct objfile *objfile;
 
   objfile = (struct objfile *) xzalloc (sizeof (struct objfile));
-  objfile->psymbol_cache = bcache_xmalloc ();
-  objfile->macro_cache = bcache_xmalloc ();
-  objfile->filename_cache = bcache_xmalloc ();
+  objfile->psymbol_cache = bcache_xmalloc (psymbol_hash, psymbol_compare);
+  objfile->macro_cache = bcache_xmalloc (NULL, NULL);
+  objfile->filename_cache = bcache_xmalloc (NULL, NULL);
   /* We could use obstack_specify_allocation here instead, but
      gdb_obstack.h specifies the alloc/dealloc functions.  */
   obstack_init (&objfile->objfile_obstack);
diff --git a/gdb/psymtab.c b/gdb/psymtab.c
index bc47681..aa7e3a1 100644
--- a/gdb/psymtab.c
+++ b/gdb/psymtab.c
@@ -1270,6 +1270,47 @@ start_psymtab_common (struct objfile *objfile,
   return (psymtab);
 }
 
+/* Calculate a hash code for the given partial symbol.  The hash is
+   calculated using the symbol's value, language, domain, class
+   and name. These are the values which are set by
+   add_psymbol_to_bcache.  */
+
+unsigned long
+psymbol_hash (const void *addr, int length)
+{
+  unsigned long h = 0;
+  struct partial_symbol *psymbol = (struct partial_symbol *) addr;
+  unsigned int lang = psymbol->ginfo.language;
+  unsigned int domain = PSYMBOL_DOMAIN (psymbol);
+  unsigned int class = PSYMBOL_CLASS (psymbol);
+
+  h = hash_continue (&psymbol->ginfo.value, sizeof (psymbol->ginfo.value), h);
+  h = hash_continue (&lang, sizeof (unsigned int), h);
+  h = hash_continue (&domain, sizeof (unsigned int), h);
+  h = hash_continue (&class, sizeof (unsigned int), h);
+  h = hash_continue (psymbol->ginfo.name, strlen (psymbol->ginfo.name), h);
+
+  return h;
+}
+
+/* Returns true if the symbol at addr1 equals the symbol at addr2.
+   For the comparison this function uses a symbols value,
+   language, domain, class and name.  */
+
+int
+psymbol_compare (const void *addr1, const void *addr2, int length)
+{
+  struct partial_symbol *sym1 = (struct partial_symbol *) addr1;
+  struct partial_symbol *sym2 = (struct partial_symbol *) addr2;
+
+  return (memcmp (&sym1->ginfo.value, &sym1->ginfo.value,
+                  sizeof (sym1->ginfo.value)) == 0
+	  && sym1->ginfo.language == sym2->ginfo.language
+          && PSYMBOL_DOMAIN (sym1) == PSYMBOL_DOMAIN (sym2)
+          && PSYMBOL_CLASS (sym1) == PSYMBOL_CLASS (sym2)
+          && sym1->ginfo.name == sym2->ginfo.name);
+}
+
 /* Helper function, initialises partial symbol structure and stashes 
    it into objfile's bcache.  Note that our caching mechanism will
    use all fields of struct partial_symbol to determine hash value of the
@@ -1285,15 +1326,8 @@ add_psymbol_to_bcache (char *name, int namelength, int copy_name,
 		       enum language language, struct objfile *objfile,
 		       int *added)
 {
-  /* psymbol is static so that there will be no uninitialized gaps in the
-     structure which might contain random data, causing cache misses in
-     bcache. */
-  static struct partial_symbol psymbol;
-
-  /* However, we must ensure that the entire 'value' field has been
-     zeroed before assigning to it, because an assignment may not
-     write the entire field.  */
-  memset (&psymbol.ginfo.value, 0, sizeof (psymbol.ginfo.value));
+  struct partial_symbol psymbol;
+
   /* val and coreaddr are mutually exclusive, one of them *will* be zero */
   if (val != 0)
     {
diff --git a/gdb/psymtab.h b/gdb/psymtab.h
index de8b67e..0786944 100644
--- a/gdb/psymtab.h
+++ b/gdb/psymtab.h
@@ -20,6 +20,9 @@
 #ifndef PSYMTAB_H
 #define PSYMTAB_H
 
+extern unsigned long psymbol_hash (const void *addr, int length);
+extern int psymbol_compare (const void *addr1, const void *addr2, int length);
+
 void map_partial_symbol_names (void (*) (const char *, void *), void *);
 
 void map_partial_symbol_filenames (void (*) (const char *, const char *,
diff --git a/gdb/symfile.c b/gdb/symfile.c
index 2cb6b7f..048b8a8 100644
--- a/gdb/symfile.c
+++ b/gdb/symfile.c
@@ -2432,11 +2432,12 @@ reread_symbols (void)
 
 	  /* Free the obstacks for non-reusable objfiles */
 	  bcache_xfree (objfile->psymbol_cache);
-	  objfile->psymbol_cache = bcache_xmalloc ();
+	  objfile->psymbol_cache = bcache_xmalloc (psymbol_hash,
+	                                           psymbol_compare);
 	  bcache_xfree (objfile->macro_cache);
-	  objfile->macro_cache = bcache_xmalloc ();
+	  objfile->macro_cache = bcache_xmalloc (NULL, NULL);
 	  bcache_xfree (objfile->filename_cache);
-	  objfile->filename_cache = bcache_xmalloc ();
+	  objfile->filename_cache = bcache_xmalloc (NULL,NULL);
 	  if (objfile->demangled_names_hash != NULL)
 	    {
 	      htab_delete (objfile->demangled_names_hash);
@@ -2458,9 +2459,10 @@ reread_symbols (void)
 	  memset (&objfile->msymbol_demangled_hash, 0,
 		  sizeof (objfile->msymbol_demangled_hash));
 
-	  objfile->psymbol_cache = bcache_xmalloc ();
-	  objfile->macro_cache = bcache_xmalloc ();
-	  objfile->filename_cache = bcache_xmalloc ();
+	  objfile->psymbol_cache = bcache_xmalloc (psymbol_hash,
+	                                           psymbol_compare);
+	  objfile->macro_cache = bcache_xmalloc (NULL, NULL);
+	  objfile->filename_cache = bcache_xmalloc (NULL, NULL);
 	  /* obstack_init also initializes the obstack so it is
 	     empty.  We could use obstack_specify_allocation but
 	     gdb_obstack.h specifies the alloc/dealloc