From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16244 invoked by alias); 16 Aug 2010 14:11:45 -0000 Received: (qmail 16229 invoked by uid 22791); 16 Aug 2010 14:11:42 -0000 X-SWARE-Spam-Status: No, hits=-5.3 required=5.0 tests=AWL,BAYES_00,KAM_STOCKGEN,RCVD_IN_DNSWL_HI,SPF_HELO_PASS,TW_BJ,T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 16 Aug 2010 14:11:04 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o7GEB3O6024436 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 16 Aug 2010 10:11:03 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o7GEB2lr023915 for ; Mon, 16 Aug 2010 10:11:03 -0400 Received: from [10.15.16.129] (dhcp-10-15-16-129.yyz.redhat.com [10.15.16.129]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id o7GEB2P9008391 for ; Mon, 16 Aug 2010 10:11:02 -0400 Message-ID: <4C6946E1.6000709@redhat.com> Date: Mon, 16 Aug 2010 14:11:00 -0000 From: sami wagiaalla User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.7) Gecko/20100720 Fedora/3.1.1-1.fc13 Thunderbird/3.1.1 MIME-Version: 1.0 To: gdb-patches@sourceware.org Subject: [RFC] Use custom hash function with bcache Content-Type: multipart/mixed; boundary="------------070403060707000907020504" X-IsSubscribed: yes Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org X-SW-Source: 2010-08/txt/msg00218.txt.bz2 This is a multi-part message in MIME format. --------------070403060707000907020504 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-length: 462 This patch enables the use of custom hash and comparison functions when adding elements to a bcache. The patch also introduces hash and comparison functions which take into consideration only the relevant properties of the psymbol. Tested by running the test suit on F13 with gcc 4.4.4 on x8664, no regressions. also used 'main print statistics' to ensure that the bcache object count and unique object count are as expected with a small test case. Sami --------------070403060707000907020504 Content-Type: text/x-patch; name="custom_hash.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="custom_hash.patch" Content-length: 8708 2010-08-13 Sami Wagiaalla * psymtab.c (psymbol_hash): New function. (psymbol_compare): New function. (add_psymbol_to_bcache): pass psymbol_hash and psymbol_compare to bcache_full. * bcache.c (hash_continue): New. (hash): Use hash_continue. (bcache): Now takes hash_function, compare_function arguments. (bcache_full): Ditto. * bcache.c (bcache): Update prototype. (bcache_full): Ditto. * macrotab.c (macro_bcache): Updated. * symfile.c (allocate_symtab): Updated. diff --git a/gdb/bcache.c b/gdb/bcache.c index 7d9180c..bef2596 100644 --- a/gdb/bcache.c +++ b/gdb/bcache.c @@ -98,12 +98,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; @@ -194,21 +201,34 @@ expand_hash_table (struct bcache *bcache) /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has never seen those bytes before, add a copy of them to BCACHE. In - either case, return a pointer to BCACHE's copy of that string. */ + either case, return a pointer to BCACHE's copy of that string. + If HASH_FUNCTION and COMPARE_FUNCTION are not NULL they will be + used for hash calculation and comparing table elements respectively. + Otherwise the hash is calculated using the byte string and a + simple byte comparison is performed. */ const void * -bcache (const void *addr, int length, struct bcache *bcache) +bcache (const void *addr, int length, struct bcache *bcache, + unsigned long (*hash_function)(const void*), + int (*compare_function)(const void*, const void*)) { - return bcache_full (addr, length, bcache, NULL); + return bcache_full (addr, length, bcache, NULL, hash_function, + compare_function); } /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has never seen those bytes before, add a copy of them to BCACHE. In either case, return a pointer to BCACHE's copy of that string. If optional ADDED is not NULL, return 1 in case of new entry or 0 if - returning an old entry. */ + returning an old entry. + If HASH_FUNCTION and COMPARE_FUNCTION are not NULL they will be + used for hash calculation and comparing table elements respectively. + Otherwise the hash is calculated using the byte string and a + simple byte comparison is performed. */ const void * -bcache_full (const void *addr, int length, struct bcache *bcache, int *added) +bcache_full (const void *addr, int length, struct bcache *bcache, int *added, + unsigned long (*hash_function)(const void*), + int (*compare_function)(const void*, const void*)) { unsigned long full_hash; unsigned short half_hash; @@ -235,7 +255,11 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added) bcache->total_count++; bcache->total_size += length; - full_hash = hash (addr, length); + if (hash_function == NULL) + full_hash = hash (addr, length); + else + full_hash = hash_function (addr); + half_hash = (full_hash >> 16); hash_index = full_hash % bcache->num_buckets; @@ -246,9 +270,18 @@ 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)) - return &s->d.data; + if (s->length == length) + { + int equal = 0; + + if (compare_function == NULL) + equal = (memcmp (&s->d.data, addr, length) == 0); + else + equal = compare_function (&s->d.data, addr); + + if (equal) + return &s->d.data; + } else bcache->half_hash_miss_count++; } diff --git a/gdb/bcache.h b/gdb/bcache.h index da69a2d..799c744 100644 --- a/gdb/bcache.h +++ b/gdb/bcache.h @@ -146,13 +146,17 @@ struct bcache; Since the cached value is ment to be read-only, return a const buffer. */ extern const void *bcache (const void *addr, int length, - struct bcache *bcache); + struct bcache *bcache, + unsigned long (*hash_function)(const void*), + int (*compare_function)(const void*, const void*)); /* Like bcache, but if ADDED is not NULL, set *ADDED to true if the bytes were newly added to the cache, or to false if the bytes were found in the cache. */ extern const void *bcache_full (const void *addr, int length, - struct bcache *bcache, int *added); + struct bcache *bcache, int *added, + unsigned long (*hash_function)(const void*), + int (*compare_function)(const void*, const void*)); /* Free all the storage used by BCACHE. */ extern void bcache_xfree (struct bcache *bcache); @@ -169,5 +173,6 @@ extern int bcache_memory_used (struct bcache *bcache); /* The hash function */ 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/macrotab.c b/gdb/macrotab.c index 93651ab..eb3eef4 100644 --- a/gdb/macrotab.c +++ b/gdb/macrotab.c @@ -109,7 +109,7 @@ static const void * macro_bcache (struct macro_table *t, const void *addr, int len) { if (t->bcache) - return bcache (addr, len, t->bcache); + return bcache (addr, len, t->bcache, NULL, NULL); else { void *copy = xmalloc (len); diff --git a/gdb/psymtab.c b/gdb/psymtab.c index bc47681..f4cdebd 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. */ + +static unsigned long +psymbol_hash (const void *addr) +{ + 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), 0); + 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. */ + +static int +psymbol_compare (const void *addr1, const void *addr2) +{ + 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) + && strcmp (sym1->ginfo.name, sym2->ginfo.name) == 0); +} + /* 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 @@ -1312,7 +1353,8 @@ add_psymbol_to_bcache (char *name, int namelength, int copy_name, /* Stash the partial symbol away in the cache */ return bcache_full (&psymbol, sizeof (struct partial_symbol), - objfile->psymbol_cache, added); + objfile->psymbol_cache, added, psymbol_hash, + psymbol_compare); } /* Helper function, adds partial symbol to the given partial symbol diff --git a/gdb/symfile.c b/gdb/symfile.c index 2cb6b7f..5e7b7c2 100644 --- a/gdb/symfile.c +++ b/gdb/symfile.c @@ -2729,7 +2729,7 @@ allocate_symtab (char *filename, struct objfile *objfile) obstack_alloc (&objfile->objfile_obstack, sizeof (struct symtab)); memset (symtab, 0, sizeof (*symtab)); symtab->filename = (char *) bcache (filename, strlen (filename) + 1, - objfile->filename_cache); + objfile->filename_cache, NULL, NULL); symtab->fullname = NULL; symtab->language = deduce_language_from_filename (filename); symtab->debugformat = "unknown"; --------------070403060707000907020504--