X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gdb%2Fbcache.c;h=a6eadd3bb96dd3f4ea631fd5923f2c10cb09c2c5;hb=c55fe0967e9ec38c1e9d9d3ffc4db30a49323302;hp=73b86e8cf53e6c3813ae7699d34d5e5248dae092;hpb=2c7ef07446ed0423f2f4bdf25b3b890175f12e2b;p=deliverable%2Fbinutils-gdb.git diff --git a/gdb/bcache.c b/gdb/bcache.c index 73b86e8cf5..a6eadd3bb9 100644 --- a/gdb/bcache.c +++ b/gdb/bcache.c @@ -2,7 +2,7 @@ Written by Fred Fish Rewritten by Jim Blandy - Copyright 1999, 2000, 2002 Free Software Foundation, Inc. + Copyright (C) 1999, 2000, 2002, 2003, 2007 Free Software Foundation, Inc. This file is part of GDB. @@ -18,17 +18,80 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ + Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ #include "defs.h" -#include "obstack.h" +#include "gdb_obstack.h" #include "bcache.h" #include "gdb_string.h" /* For memcpy declaration */ +#include "gdb_assert.h" #include #include +/* The type used to hold a single bcache string. The user data is + stored in d.data. Since it can be any type, it needs to have the + same alignment as the most strict alignment of any type on the host + machine. I don't know of any really correct way to do this in + stock ANSI C, so just do it the same way obstack.h does. */ + +struct bstring +{ + /* Hash chain. */ + struct bstring *next; + /* Assume the data length is no more than 64k. */ + unsigned short length; + /* The half hash hack. This contains the upper 16 bits of the hash + value and is used as a pre-check when comparing two strings and + avoids the need to do length or memcmp calls. It proves to be + roughly 100% effective. */ + unsigned short half_hash; + + union + { + char data[1]; + double dummy; + } + d; +}; + + +/* The structure for a bcache itself. The bcache is initialized, in + bcache_xmalloc(), by filling it with zeros and then setting the + corresponding obstack's malloc() and free() methods. */ + +struct bcache +{ + /* All the bstrings are allocated here. */ + struct obstack cache; + + /* How many hash buckets we're using. */ + unsigned int num_buckets; + + /* Hash buckets. This table is allocated using malloc, so when we + grow the table we can return the old table to the system. */ + struct bstring **bucket; + + /* Statistics. */ + unsigned long unique_count; /* number of unique strings */ + long total_count; /* total number of strings cached, including dups */ + long unique_size; /* size of unique strings, in bytes */ + long total_size; /* total number of bytes cached, including dups */ + long structure_size; /* total size of bcache, including infrastructure */ + /* Number of times that the hash table is expanded and hence + re-built, and the corresponding number of times that a string is + [re]hashed as part of entering it into the expanded table. The + total number of hashes can be computed by adding TOTAL_COUNT to + expand_hash_count. */ + unsigned long expand_count; + unsigned long expand_hash_count; + /* Number of times that the half-hash compare hit (compare the upper + 16 bits of hash values) hit, but the corresponding combined + length/data compare missed. */ + unsigned long half_hash_miss_count; +}; + /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now, * and is better than the old one. */ @@ -73,6 +136,11 @@ expand_hash_table (struct bcache *bcache) struct bstring **new_buckets; unsigned int i; + /* Count the stats. Every unique item needs to be re-hashed and + re-entered. */ + bcache->expand_count++; + bcache->expand_hash_count += bcache->unique_count; + /* Find the next size. */ new_num_buckets = bcache->num_buckets * 2; for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++) @@ -127,9 +195,11 @@ 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. */ -void * -bcache (const void *addr, int length, struct bcache *bcache) +static void * +bcache_data (const void *addr, int length, struct bcache *bcache) { + unsigned long full_hash; + unsigned short half_hash; int hash_index; struct bstring *s; @@ -140,13 +210,24 @@ bcache (const void *addr, int length, struct bcache *bcache) bcache->total_count++; bcache->total_size += length; - hash_index = hash (addr, length) % bcache->num_buckets; + full_hash = hash (addr, length); + half_hash = (full_hash >> 16); + hash_index = full_hash % bcache->num_buckets; - /* Search the hash bucket for a string identical to the caller's. */ + /* Search the hash bucket for a string identical to the caller's. + As a short-circuit first compare the upper part of each hash + values. */ for (s = bcache->bucket[hash_index]; s; s = s->next) - if (s->length == length - && ! memcmp (&s->d.data, addr, length)) - return &s->d.data; + { + if (s->half_hash == half_hash) + { + if (s->length == length + && ! memcmp (&s->d.data, addr, length)) + return &s->d.data; + else + bcache->half_hash_miss_count++; + } + } /* The user's string isn't in the list. Insert it after *ps. */ { @@ -155,6 +236,7 @@ bcache (const void *addr, int length, struct bcache *bcache) memcpy (&new->d.data, addr, length); new->length = length; new->next = bcache->bucket[hash_index]; + new->half_hash = half_hash; bcache->bucket[hash_index] = new; bcache->unique_count++; @@ -165,20 +247,41 @@ bcache (const void *addr, int length, struct bcache *bcache) } } +void * +deprecated_bcache (const void *addr, int length, struct bcache *bcache) +{ + return bcache_data (addr, length, bcache); +} + +const void * +bcache (const void *addr, int length, struct bcache *bcache) +{ + return bcache_data (addr, length, bcache); +} -/* Freeing bcaches. */ +/* Allocating and freeing bcaches. */ + +struct bcache * +bcache_xmalloc (void) +{ + /* Allocate the bcache pre-zeroed. */ + struct bcache *b = XCALLOC (1, struct bcache); + /* We could use obstack_specify_allocation here instead, but + gdb_obstack.h specifies the allocation/deallocation + functions. */ + obstack_init (&b->cache); + return b; +} /* Free all the storage associated with BCACHE. */ void -free_bcache (struct bcache *bcache) +bcache_xfree (struct bcache *bcache) { + if (bcache == NULL) + return; obstack_free (&bcache->cache, 0); - if (bcache->bucket) - xfree (bcache->bucket); - - /* This isn't necessary, but at least the bcache is always in a - consistent state. */ - memset (bcache, 0, sizeof (*bcache)); + xfree (bcache->bucket); + xfree (bcache); } @@ -198,9 +301,10 @@ static void print_percentage (int portion, int total) { if (total == 0) - printf_filtered ("(not applicable)\n"); + /* i18n: Like "Percentage of duplicates, by count: (not applicable)" */ + printf_filtered (_("(not applicable)\n")); else - printf_filtered ("%3d%%\n", portion * 100 / total); + printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total)); } @@ -214,12 +318,16 @@ print_bcache_statistics (struct bcache *c, char *type) int occupied_buckets; int max_chain_length; int median_chain_length; + int max_entry_size; + int median_entry_size; - /* Count the number of occupied buckets, and measure chain lengths. */ + /* Count the number of occupied buckets, tally the various string + lengths, and measure chain lengths. */ { unsigned int b; - int *chain_length - = (int *) alloca (c->num_buckets * sizeof (*chain_length)); + int *chain_length = XCALLOC (c->num_buckets + 1, int); + int *entry_size = XCALLOC (c->unique_count + 1, int); + int stringi = 0; occupied_buckets = 0; @@ -235,7 +343,10 @@ print_bcache_statistics (struct bcache *c, char *type) while (s) { + gdb_assert (b < c->num_buckets); chain_length[b]++; + gdb_assert (stringi < c->unique_count); + entry_size[stringi++] = s->length; s = s->next; } } @@ -244,6 +355,8 @@ print_bcache_statistics (struct bcache *c, char *type) /* To compute the median, we need the set of chain lengths sorted. */ qsort (chain_length, c->num_buckets, sizeof (chain_length[0]), compare_ints); + qsort (entry_size, c->unique_count, sizeof (entry_size[0]), + compare_ints); if (c->num_buckets > 0) { @@ -255,39 +368,75 @@ print_bcache_statistics (struct bcache *c, char *type) max_chain_length = 0; median_chain_length = 0; } + if (c->unique_count > 0) + { + max_entry_size = entry_size[c->unique_count - 1]; + median_entry_size = entry_size[c->unique_count / 2]; + } + else + { + max_entry_size = 0; + median_entry_size = 0; + } + + xfree (chain_length); + xfree (entry_size); } - printf_filtered (" Cached '%s' statistics:\n", type); - printf_filtered (" Total object count: %ld\n", c->total_count); - printf_filtered (" Unique object count: %lu\n", c->unique_count); - printf_filtered (" Percentage of duplicates, by count: "); + printf_filtered (_(" Cached '%s' statistics:\n"), type); + printf_filtered (_(" Total object count: %ld\n"), c->total_count); + printf_filtered (_(" Unique object count: %lu\n"), c->unique_count); + printf_filtered (_(" Percentage of duplicates, by count: ")); print_percentage (c->total_count - c->unique_count, c->total_count); printf_filtered ("\n"); - printf_filtered (" Total object size: %ld\n", c->total_size); - printf_filtered (" Unique object size: %ld\n", c->unique_size); - printf_filtered (" Percentage of duplicates, by size: "); + printf_filtered (_(" Total object size: %ld\n"), c->total_size); + printf_filtered (_(" Unique object size: %ld\n"), c->unique_size); + printf_filtered (_(" Percentage of duplicates, by size: ")); print_percentage (c->total_size - c->unique_size, c->total_size); printf_filtered ("\n"); - printf_filtered (" Total memory used by bcache, including overhead: %ld\n", + printf_filtered (_(" Max entry size: %d\n"), max_entry_size); + printf_filtered (_(" Average entry size: ")); + if (c->unique_count > 0) + printf_filtered ("%ld\n", c->unique_size / c->unique_count); + else + /* i18n: "Average entry size: (not applicable)" */ + printf_filtered (_("(not applicable)\n")); + printf_filtered (_(" Median entry size: %d\n"), median_entry_size); + printf_filtered ("\n"); + + printf_filtered (_(" Total memory used by bcache, including overhead: %ld\n"), c->structure_size); - printf_filtered (" Percentage memory overhead: "); + printf_filtered (_(" Percentage memory overhead: ")); print_percentage (c->structure_size - c->unique_size, c->unique_size); - printf_filtered (" Net memory savings: "); + printf_filtered (_(" Net memory savings: ")); print_percentage (c->total_size - c->structure_size, c->total_size); printf_filtered ("\n"); - printf_filtered (" Hash table size: %3d\n", c->num_buckets); - printf_filtered (" Hash table population: "); + printf_filtered (_(" Hash table size: %3d\n"), c->num_buckets); + printf_filtered (_(" Hash table expands: %lu\n"), + c->expand_count); + printf_filtered (_(" Hash table hashes: %lu\n"), + c->total_count + c->expand_hash_count); + printf_filtered (_(" Half hash misses: %lu\n"), + c->half_hash_miss_count); + printf_filtered (_(" Hash table population: ")); print_percentage (occupied_buckets, c->num_buckets); - printf_filtered (" Median hash chain length: %3d\n", + printf_filtered (_(" Median hash chain length: %3d\n"), median_chain_length); - printf_filtered (" Average hash chain length: "); + printf_filtered (_(" Average hash chain length: ")); if (c->num_buckets > 0) printf_filtered ("%3lu\n", c->unique_count / c->num_buckets); else - printf_filtered ("(not applicable)\n"); - printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length); + /* i18n: "Average hash chain length: (not applicable)" */ + printf_filtered (_("(not applicable)\n")); + printf_filtered (_(" Maximum hash chain length: %3d\n"), max_chain_length); printf_filtered ("\n"); } + +int +bcache_memory_used (struct bcache *bcache) +{ + return obstack_memory_used (&bcache->cache); +}