gdb/bcache.c

   1 /* Implement a cached obstack.
   2    Written by Fred Fish <fnf@cygnus.com>
   3    Rewritten by Jim Blandy <jimb@cygnus.com>
   4
   5    Copyright 1999, 2000, 2002 Free Software Foundation, Inc.
   6
   7    This file is part of GDB.
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place - Suite 330,
  22    Boston, MA 02111-1307, USA.  */
  23
  24 #include "defs.h"
  25 #include "obstack.h"
  26 #include "bcache.h"
  27 #include "gdb_string.h"         /* For memcpy declaration */
  28
  29 #include <stddef.h>
  30 #include <stdlib.h>
  31
  32 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
  33  * and is better than the old one.
  34  */
  35 \f
  36 unsigned long
  37 hash(const void *addr, int length)
  38 {
  39                 const unsigned char *k, *e;
  40                 unsigned long h;
  41
  42                 k = (const unsigned char *)addr;
  43                 e = k+length;
  44                 for (h=0; k< e;++k)
  45                 {
  46                                 h *=16777619;
  47                                 h ^= *k;
  48                 }
  49                 return (h);
  50 }
  51 \f
  52 /* Growing the bcache's hash table.  */
  53
  54 /* If the average chain length grows beyond this, then we want to
  55    resize our hash table.  */
  56 #define CHAIN_LENGTH_THRESHOLD (5)
  57
  58 static void
  59 expand_hash_table (struct bcache *bcache)
  60 {
  61   /* A table of good hash table sizes.  Whenever we grow, we pick the
  62      next larger size from this table.  sizes[i] is close to 1 << (i+10),
  63      so we roughly double the table size each time.  After we fall off
  64      the end of this table, we just double.  Don't laugh --- there have
  65      been executables sighted with a gigabyte of debug info.  */
  66   static unsigned long sizes[] = {
  67     1021, 2053, 4099, 8191, 16381, 32771,
  68     65537, 131071, 262144, 524287, 1048573, 2097143,
  69     4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
  70     268435459, 536870923, 1073741827, 2147483659UL
  71   };
  72   unsigned int new_num_buckets;
  73   struct bstring **new_buckets;
  74   unsigned int i;
  75
  76   /* Find the next size.  */
  77   new_num_buckets = bcache->num_buckets * 2;
  78   for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
  79     if (sizes[i] > bcache->num_buckets)
  80       {
  81         new_num_buckets = sizes[i];
  82         break;
  83       }
  84
  85   /* Allocate the new table.  */
  86   {
  87     size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
  88     new_buckets = (struct bstring **) xmalloc (new_size);
  89     memset (new_buckets, 0, new_size);
  90
  91     bcache->structure_size -= (bcache->num_buckets
  92                                * sizeof (bcache->bucket[0]));
  93     bcache->structure_size += new_size;
  94   }
  95
  96   /* Rehash all existing strings.  */
  97   for (i = 0; i < bcache->num_buckets; i++)
  98     {
  99       struct bstring *s, *next;
 100
 101       for (s = bcache->bucket[i]; s; s = next)
 102         {
 103           struct bstring **new_bucket;
 104           next = s->next;
 105
 106           new_bucket = &new_buckets[(hash (&s->d.data, s->length)
 107                                      % new_num_buckets)];
 108           s->next = *new_bucket;
 109           *new_bucket = s;
 110         }
 111     }
 112
 113   /* Plug in the new table.  */
 114   if (bcache->bucket)
 115     xfree (bcache->bucket);
 116   bcache->bucket = new_buckets;
 117   bcache->num_buckets = new_num_buckets;
 118 }
 119
 120 \f
 121 /* Looking up things in the bcache.  */
 122
 123 /* The number of bytes needed to allocate a struct bstring whose data
 124    is N bytes long.  */
 125 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
 126
 127 /* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
 128    never seen those bytes before, add a copy of them to BCACHE.  In
 129    either case, return a pointer to BCACHE's copy of that string.  */
 130 void *
 131 bcache (const void *addr, int length, struct bcache *bcache)
 132 {
 133   int hash_index;
 134   struct bstring *s;
 135
 136   /* If our average chain length is too high, expand the hash table.  */
 137   if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
 138     expand_hash_table (bcache);
 139
 140   bcache->total_count++;
 141   bcache->total_size += length;
 142
 143   hash_index = hash (addr, length) % bcache->num_buckets;
 144
 145   /* Search the hash bucket for a string identical to the caller's.  */
 146   for (s = bcache->bucket[hash_index]; s; s = s->next)
 147     if (s->length == length
 148         && ! memcmp (&s->d.data, addr, length))
 149       return &s->d.data;
 150
 151   /* The user's string isn't in the list.  Insert it after *ps.  */
 152   {
 153     struct bstring *new
 154       = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
 155     memcpy (&new->d.data, addr, length);
 156     new->length = length;
 157     new->next = bcache->bucket[hash_index];
 158     bcache->bucket[hash_index] = new;
 159
 160     bcache->unique_count++;
 161     bcache->unique_size += length;
 162     bcache->structure_size += BSTRING_SIZE (length);
 163
 164     return &new->d.data;
 165   }
 166 }
 167
 168 \f
 169 /* Freeing bcaches.  */
 170
 171 /* Free all the storage associated with BCACHE.  */
 172 void
 173 free_bcache (struct bcache *bcache)
 174 {
 175   obstack_free (&bcache->cache, 0);
 176   if (bcache->bucket)
 177     xfree (bcache->bucket);
 178
 179   /* This isn't necessary, but at least the bcache is always in a
 180      consistent state.  */
 181   memset (bcache, 0, sizeof (*bcache));
 182 }
 183
 184
 185 \f
 186 /* Printing statistics.  */
 187
 188 static int
 189 compare_ints (const void *ap, const void *bp)
 190 {
 191   /* Because we know we're comparing two ints which are positive,
 192      there's no danger of overflow here.  */
 193   return * (int *) ap - * (int *) bp;
 194 }
 195
 196
 197 static void
 198 print_percentage (int portion, int total)
 199 {
 200   if (total == 0)
 201     printf_filtered ("(not applicable)\n");
 202   else
 203     printf_filtered ("%3d%%\n", portion * 100 / total);
 204 }
 205
 206
 207 /* Print statistics on BCACHE's memory usage and efficacity at
 208    eliminating duplication.  NAME should describe the kind of data
 209    BCACHE holds.  Statistics are printed using `printf_filtered' and
 210    its ilk.  */
 211 void
 212 print_bcache_statistics (struct bcache *c, char *type)
 213 {
 214   int occupied_buckets;
 215   int max_chain_length;
 216   int median_chain_length;
 217
 218   /* Count the number of occupied buckets, and measure chain lengths.  */
 219   {
 220     unsigned int b;
 221     int *chain_length
 222       = (int *) alloca (c->num_buckets * sizeof (*chain_length));
 223
 224     occupied_buckets = 0;
 225
 226     for (b = 0; b < c->num_buckets; b++)
 227       {
 228         struct bstring *s = c->bucket[b];
 229
 230         chain_length[b] = 0;
 231
 232         if (s)
 233           {
 234             occupied_buckets++;
 235
 236             while (s)
 237               {
 238                 chain_length[b]++;
 239                 s = s->next;
 240               }
 241           }
 242       }
 243
 244     /* To compute the median, we need the set of chain lengths sorted.  */
 245     qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
 246            compare_ints);
 247
 248     if (c->num_buckets > 0)
 249       {
 250         max_chain_length = chain_length[c->num_buckets - 1];
 251         median_chain_length = chain_length[c->num_buckets / 2];
 252       }
 253     else
 254       {
 255         max_chain_length = 0;
 256         median_chain_length = 0;
 257       }
 258   }
 259
 260   printf_filtered ("  Cached '%s' statistics:\n", type);
 261   printf_filtered ("    Total object count:  %ld\n", c->total_count);
 262   printf_filtered ("    Unique object count: %lu\n", c->unique_count);
 263   printf_filtered ("    Percentage of duplicates, by count: ");
 264   print_percentage (c->total_count - c->unique_count, c->total_count);
 265   printf_filtered ("\n");
 266
 267   printf_filtered ("    Total object size:   %ld\n", c->total_size);
 268   printf_filtered ("    Unique object size:  %ld\n", c->unique_size);
 269   printf_filtered ("    Percentage of duplicates, by size:  ");
 270   print_percentage (c->total_size - c->unique_size, c->total_size);
 271   printf_filtered ("\n");
 272
 273   printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
 274                    c->structure_size);
 275   printf_filtered ("    Percentage memory overhead: ");
 276   print_percentage (c->structure_size - c->unique_size, c->unique_size);
 277   printf_filtered ("    Net memory savings:         ");
 278   print_percentage (c->total_size - c->structure_size, c->total_size);
 279   printf_filtered ("\n");
 280
 281   printf_filtered ("    Hash table size:           %3d\n", c->num_buckets);
 282   printf_filtered ("    Hash table population:     ");
 283   print_percentage (occupied_buckets, c->num_buckets);
 284   printf_filtered ("    Median hash chain length:  %3d\n",
 285                    median_chain_length);
 286   printf_filtered ("    Average hash chain length: ");
 287   if (c->num_buckets > 0)
 288     printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
 289   else
 290     printf_filtered ("(not applicable)\n");
 291   printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
 292   printf_filtered ("\n");
 293 }